There is a salsa dance class going on at Da-iict :). There are 2n students participating in the class. They have to form n teams of two students each so that the dance may begin. It is possible that two boys/girls are in the same team. Can you find out in how many ways the teams can be formed.

Input

The first line will be T (T<=10) which denotes the number of test cases.  Each of the next T lines will have the number n (0<=n<=17)

Output

For each test case output the answer on a new line. Answer will always fit in a 64 bit signed data type.

Example

Input:
3
3
1
2
3

Output:
1
3
15

Explanation: For n = 1 , there are only 2 students. Hence only 1 way to form a team.