Dr.Dawood is another mathematician who is more geekier than Osama (that's why, ++). Dawood deals with more complex problems than Osama usually deals with. He also recruits people to be his sub-ordinates. He usually gives them "trivial" problems as test for them to solve and earn their position to be his sub-ordinate.

You went to attend such a test and you were given the following question.

Lets define a function A(N,K) where it signifies the number of ways in which we can draw K objects from a pool of N objects.

Lets define another function B(x1,x2,x3,x4,...) where it signifies the largest integer which can perfectly divide all the integers x1,x2,x3,...

Using these two functions , Dawood gave you a problem. The problem is stated as follows..

Given an integer N find the value of the equation,

O = B(A(2N,1),A(2N,3),A(2N,5),....,A(2N,(2*N)-1)

Input consists of T in the first line, which is the total number of testcases to be processed. Followed by T lines of inputs. Each testcase consists of value N.

Output the value of the equation O in a new line.

1 <= T <= 1000

1 <= N <= 10^12