SALSA - Salsa Dance

no tags 

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.

hide comments
impulse: 2011-06-07 04:58:03

lol, there is tricky case, i need 2 time to get ac


Added by:Siddharth Kothari
Date:2010-10-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Ishani Parekh