It is an interesting problem to count the number of unordered partitions of a number N.
This is generally done by putting N non-negative numbers in non-increasing order along a 1xN board, which sum to N.
In this problem however, you are given a 2xN board. You need to fill in non-negative numbers in this board in such a way, that
(1) The sum of all the numbers filled = N
(2) Each of the 2 rows consist of numbers in non-increasing order
(3) Each of the N columns consist of numbers in non-increasing order.
In how many ways can this be done, given the number N? Two ways are considered different if there is a cell in the board which has different numbers.
Input:
The first line consists of the number of testcases T. Each testcase consists of a single integer N.
Output:
For each testcase, output a single line, giving the number of ways.
Constraints:
T <= 10
N <= 70
The answer will fit in a 64 bit signed integer.
Sample Input:
1
5
Sample Output:
16
