CSP-J 树与二叉树公式计算

题目描述

给出若干个查询，根据 CSP-J 树与二叉树常用公式输出答案。

查询类型说明：

• TREE n：一棵 n 个节点的树有多少条边。
• FOREST n k：n 个节点、k 棵树的森林有多少条边。
• LAYER k：二叉树第 k 层最多有多少个节点，根为第 1 层。
• MAXNODE h：高度为 h 的二叉树最多有多少个节点。
• PARENT i：从 1 开始编号的完全二叉树中，节点 i 的父节点下标。
• FULLLEAF h：高度为 h 的完美二叉树有多少个叶子节点。

输入格式

第一行一个整数 q。接下来 q 行，每行一个查询。

输出格式

每个查询输出一行答案。

样例

输入样例 1

6
TREE 20
FOREST 15 4
LAYER 5
MAXNODE 5
PARENT 9
FULLLEAF 4

输出样例 1

19
11
16
31
4
8

数据范围与提示

1≤q≤100，所有结果在 64 位整数范围内。