Ural1142 Relation

时间限制:1s      空间限制:128MB

题目描述


dnc1994要用"<"和"="两种符号连接变量,一个合法的方案必须满足:
1) 大小关系符合逻辑;
2) 形如 A = B < C 与 B = A < C 的两个方案被认为相同。
现在dnc1994请你求出连接N个变量的方案数。

比如连接 A、B、C 3个变量,有如下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


输入格式


第一行一个正整数TEST(1 <= TEST <= 1000),表示数据组数。
接下来TEST行,每行一个正整数(1 <= N <= 50),表示变量的个数。


输出格式

输出TEST行,每行一个整数表示方案数。


样例输入

2
1
3



样例输出

1
13

提示

没有写明提示


题目来源

没有写明来源