Shake It

Shoaib, Tashreef, Rifat and Parvez have entered a race competition as team and successfully become champion on behalf of AUST. The judges asked each of them to seat in a round table and to handshake with other simultaneously in such a way that none of them cross each other before taking prizes. While doing this, an interesting problem came to Shoaib’s mind. In how may ways this can be performed at a fixed position if there are 2N number of people? As an example, for 4 ( here, N =2) of them the answer is 2 (Illustrated in following diagram). Shoaib is currently busy celebrating the win. So, he seeks your help. Please note that noone can seat idly. That means one must handshake with another person.

Input

The first line contains an integer T denoting the number of test cases. Each of the test cases starts with an integer, S that indicates the number of Ns under a particular test case. The next S lines will contain one integer, N.

• 1 ≤ T ≤ 100
• 1 ≤ S ≤ 16
• 1 ≤ N≤ 16

Output

Print a number denoting the number of ways. Print an extra new line after each test case.

Sample

1
3
4
1
2

14
1
2