#1559 HandsShaking

63  1 s   128 MB  

Description

Consider a meeting of N distinguishable businessmen sitting around a circular table. To start the meeting, they must shake hands. Each businessman shakes the hand of exactly one other businessman. All handshakes happen simultaneously. We say that the shake is perfect if no arms cross each other. Given an int N, return the number of perfect shakes that exist for N businessmen. For example, there are two out of three ways for the case of N = 4:

 

Input

The first line of the input gives the number of test cases, T. Then, T test cases follow. The first line of each test cases contains an even integer N (2 ≤ N ≤ 50) .

 

Output

For each test case, output the answer on a separate line.

 

Sample Input

Sample Output

3
2
4
8
1
2
14