Alice loves playing with match sticks and making objects out of it. She has been given 2*n match sticks and is asked to make hills out of it. The problem is there can be multiple such possible hills of varying heights. The match sticks can only be kept in either 45 degree angle or 135 degree angle which represents an uphill or a downhill respectively. Alice will be given 2*n match sticks, there has to be exactly n number of "uphill" match sticks (45 degree) and "downhill" match sticks (135 degree). You have to predict how many possible combination of hills Alice can come up with.
The first line of test file contains the number of test cases to follow (t). The second line contains total number of match sticks (m) that will be given to Alice. Note that 'm' will always be even.
For each test case, output a line containing the number of possible hills Alice can come up with.
Problem Setter: Anjali Singh