This is probably the easiest task of this problem set. To help you understand the task let us define two key functions:

f(n,k), (with k <= n) which gives the number of ways we can draw a sample of k objects from a set of n-distinct objects where order of drawing is not important and we do not allow repetition.

G(x1, x2, x3, … , xn) is the largest integer that perfectly divides all of {x1, x2, x3, … , xn}.

Given an integer N, your task is to compute the value of Y where

```
Y = G( f(2*N,1), f(2*N,3), f(2*N,5), ... , f(2*N,2*N-1)).
```

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first and the only line of each test case contains a single integer denoting the given N as described in the problem statement.

Output

For each test case, output a single line containing the value of Y.

Constraints

1 ≤ T ≤ 10000

2 ≤ N ≤ 1011

Example

Input:

3

6

5

4

Output:

4

2

8

i have tried it but could not get AC.Please provide a good algorithm!