阶数为 $n$ 的硬币系统是指一个由不超过 $n$ 的正整数组成的集合，这些正整数即为硬币的面值。对于一个给定的正整数金额，如果它能表示为若干硬币面值的和（每种面值可以使用多次），则称该金额对于给定的硬币系统是可表示的。

例如，考虑硬币系统 $\{3, 4\}$。不难发现，除了 $1, 2$ 和 $5$ 之外，所有正整数都是可表示的，而这三个数不可表示。

如果存在一个阶数为 $n$ 的硬币系统，使得该集合中的所有整数都是可表示的，且所有其他正整数均不可表示，则称该正整数集合为阶数为 $n$ 的成本集。例如，$\{3, 4, 6, 7, 8, 9, \dots\}$ 是阶数为 $4$ 的成本集，但不是阶数为 $3$ 的成本集。注意，空集是任意阶数的成本集，对应于空的硬币系统。

给定阶数 $n$，求有多少种不同的成本集？

输入格式

输入文件的第一行包含测试用例的数量 $t$，$1 \le t \le 63$。接下来的 $t$ 行，每行包含一个整数 $n$，$1 \le n \le 63$，表示需要计算的成本集的阶数。

输出格式

对于每个测试用例，输出一行，包含阶数为 $n$ 的不同成本集的数量。

样例

样例输入 1

2
1
2

样例输出 1

2
3