题目描述

dnc1994 要用 < 和 = 两种符号连接变量，一个合法的方案必须满足：

• 大小关系符合逻辑；
• 形如 $a=b<c$ 与 $b=a<c$ 的两个方案被认为相同。

现在 dnc1994 请你求出连接 $n$ 个变量的方案数。

比如连接 $a,b,c$ 三个变量，有如下 13 种方案：

1. $a=b=c$
2. $a=b<c$
3. $a<b=c$
4. $a<b<c$
5. $a<c<b$
6. $a=c<b$
7. $b<a=c$
8. $b<a<c$
9. $b<c<a$
10. $b=c<a$
11. $c<a=b$
12. $c<a<b$
13. $c<b<a$

输入格式

第一行一个正整数 $T$，表示数据组数。
接下来 $T$ 行，每行一个正整数 $n$，表示变量的个数。

输出格式

共 $T$ 行，每行一个整数表示答案。

2
1
3

1
13

数据规模与约定

对于 $100\%$ 的数据，$1\leq T\leq 10^3$，$1\leq n\leq 50$。