Problem Description

Have become a sophomore, WNJXYK found that his recent combinatorial mathematics homework is too hard. Homework always matters a lot. To get high grades, he has no choice but to ask you for help.
Here is the problem: Can you calculate the numbers of ways to put 2$n$ different balls into exact same boxes and each box contains exactly 2 balls.

Input

The input starts with one line contains exactly one positive integer $T$ which is the number of test cases.
Each test case contains one line with exactly one positive integer $n$ which has been explained above.

Output

For each test case, output one line containing “y” where y is the number of different ways modulo 2^64.

3
1
2
100

1
3
7119879074588212521

Hint

1<=T<=10,1<=N<=10^18
For test case 1, it is obviously that there is only one way to do so.
For test case 2, we could assume that 4 different are indexed from 1 to 4. Three different splitting ways are {{1,2}, {3,4}}, {{1,3}, {2,4}} and {{1,4}, {2,3}}.