ques---------->

The captain of the ship TITANIC is a little .... off the track. He needs to select the crew for the ship. But everyone seems to be eligible. So to test their intelligence, he plays a game.
The contestants have to stand in a line. They are given the numbers in the order in which they stand, starting from 1. The captain then removes all the contestants that are standing at an odd position.
Initially, standing people have numbers - 1,2,3,4,5...
After first pass, people left are - 2,4,...
After second pass - 4,....
And so on.
You want to board the ship as a crew member. Given the total number of applicants for a position, find the best place to stand in the line so that you are selected.

Input

First line contains the number of test cases t (t<=10^6). The next t lines contain integer n, the number of applicants for that case. (n<=10^9)

Output

Display t lines, each containg a single integer, the place where you would stand to win a place at TITANIC.

Example

Input:
2
5
12

output

4

8

soln---------->

#include<iostream>

using namespace std;

int output(long long int *,long long int);
void removeodd(long long int *arr,long long int b)
{
     long long int arr2[b],j,k=2;
     if(b%2!=0)
               {
                for(j=1;j<=b;j++)
                                 {
                                 arr2[j]=arr[k];
                                 k+=2;
                                 }
                output(arr2,b);
                }
     else
                {
                 for(j=1;j<=b-1;j++)
                                    {
                                    arr2[j]=arr[k];
                                    k+=2;
                                    }
                 output(arr2,b);
                }
}
int output(long long int *arr,long long int b)
{
     if(b%2==0)
               {        
                          if((b/2)==1)
                          cout<<arr[1]<<"\n";
                          else
                          removeodd(arr,b/2);    
               }
     else
               {        
                         if((b/2+1)==1)
                         cout<<arr[1];
                         else
                         removeodd(arr,(b/2+1));    
               }    
}
int main()
{   unsigned long n;
    cin>>n;
    long long int b[n];
    for(long long int g=1;g<=n;g++)
    {
    cin>>b[g];
    }
    for(long long int f=1;f<=n;f++)
    {
    long long int arr[b[f]];
    for(long long int i=1;i<=b[f];i++)
    arr[i]=i;
    output(arr,b[f]);
    }
    system("pause");
}