Consider a square matrix of order m (m+1 rows and m+1 columns). At each step you can move one step to the right or one step to the top. How many possibilities are to reach (m, m) from (0, 0)?

Input

The first line consists of an integer t, the number of test cases. Each test case consists of a single integer m, the order of square matrix.

Output

For each case print the number of possibilities of reaching the point (m, m) from (0, 0)

Constraints

1 ≤ t ≤ 10

1 ≤ m ≤ 14

Example

Sample Input:
3
1
2
3

Sample Output:
2
6
20

Explanation of Test Cases 1 and 2

See Also : WAYS (No source limit)