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:
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) .
For each test case, output the answer on a separate line.
3 2 4 8
1 2 14