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 there 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 ways of reaching the point (m, m) from (0, 0)

Constraints

1 ≤ t ≤ 10

1 ≤ m ≤ 14

Example

Input:
3
1
2
3

Output:
2
6
20

Explanation of Test Cases 1 and 2