Monk lives in a planet where value of currency coins are in non-negative powers of 2 (i.e. 1, 2, 4, 8, 16 and so on). Today he goes to ATM for withdrawing money.

But the ATM machine follows some specific rules given below:

1. The ATM machine gives a maximum of one coin in one transaction.

2. The ATM machine shows a number N on the screen for each transaction.

3. Monk has to enter a number called PIN number for each transaction.

4. Then the ATM machine follows the function defined below.

5. If the return value of function is 0, then no coin is withdrawn from ATM machine.

6. If the return value of function is greater than 0, then the coin withdrawn has value equal to the return value of the function.

int fun(int N,int PIN) 
        {   
            if(N%PIN!=0) 
            return 0;

            M=N/PIN;        
            int value=0;    
            for(i=1;i<=M;i++) { 
                if(gcd(i,M)==i) 
                value++; 
               }        

            if(isPowerof2(value))
            return value; 
            else     
            return 0;
         }  

Monk wants to make T transactions and for each transaction he wants to withdraw a coin of maximum possible value under the given constraints. But he does not know about the function, so he needs your help.

You have to select a PIN number such that Monk gets maximum valued coin for each transaction. You have to print the maximum possible value of the coin withdrawn for each transaction only.

Input:

The first line of the input will contain T , the number of transactions.

Next T lines will contain an integer N .

Output:

For each test-case , output the answer in a separate line

Constraints:

$1 \le T \le 10^5$

$1 \le N \le 10^7$