Chandu has been appointed as the superintendent of a jail having N prisoners .

Prisoner are numbered form 1 to N.
Today he has been specially invited to execute the prisoners.

All the prisoners are arranged in circle and he starts executing them in clock-wise direction. He always starts with first prisoner and skips
the first prisoner and execute the second, skips the third and execute the fourth and so on.

He stops executing only when one prisoner is left.

Now Chanchal being a curious man wanted to find the last prisoner who will not be executed.

He wants to write a program for it.
Help him to find his answer quickly.

INPUT

First line contain T number of test cases.

Next T lines contain number N .

OUTPUT

Print T lines of output denoting the last prisoner.

CONSTRAINTS

1 ≤ T ≤ 10000

1 ≤ N ≤ 100000

SAMPLE INPUT
2
5
6

SAMPLE OUTPUT
3
5
st1=int(raw_input())
while(st1!=0):
    ans=1
    n=int(raw_input())
    k=2
    for i in range(n):
        ans=(ans+k-1)%(i+1)+1
    print(ans)
    st1=st1-1