Problem in solving The easiest problem (bingcd) of Code Zip 2013 .

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!

U just have to print the highest power of 2 that can perfectly divide 2*n…this can be seen easily if u try out a few examples on paper…lets take 2 cases…1st n=4 and then n=5…

Case1 n=4:

2*n=8

8C1=8 8C3=56 8C5=56 8C7=8

here the highest power of 2 that can divide all the numbers is 8…i.e. GCD…and it is the same number that is the highest power of 2 that can divide 2*n!!!

Case2 n=5:

2*n=10

10C1=10 10C3=120 10C5=252 10C7=120 10C9=10

here the highest power of 2 that can divide all the numbers is 2…i.e. GCD…and it is the same number that is the highest power of 2 that can divide 2*n!!!

you can try more examples on paper…hope this helps…:slight_smile:

1 Like

:stuck_out_tongue: … it was easy.

glad could help though…:stuck_out_tongue:

I got your method,but unable to understand the logic behind it…

//