Ural1142 Relation

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

1. 大小关系符合逻辑；
2. 形如 $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

输入格式

第一行一个正整数 $\mathit{TEST}$，表示数据组数。

接下来 $\mathit{TEST}$ 行，每行一个正整数 $N$，表示变量的个数。

输出格式

输出 $\mathit{TEST}$ 行，每行一个整数表示方案数。

样例输入

2
1
3

样例输出

1
13

数据范围

• $1\le \mathit{TEST}\le 1000$；
• $1\le N\le 50$。

来源与许可

本题题面与测试数据整理自 BZOJ 2786。

样例 1

输入

2
1
3

输出

1
13