#2786. Ural1142 Relation

题目描述

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  

数据范围与提示