Problem Description 

You are an army personnel in the great army of the Zorin race, where you are a part of a team of n people.
Unfortunately, your army has lost a war to an intergalactic species, genetically much advanced than yours.
Their captain Bruno have kept all your men (including you) as hostages, and now they are trying to have some fun.
He asks each of the n people to choose any integer from 1 to n that is not taken by someone else. i.e. no two persons can have the same chosen number. Then he arranges all the n people in a circle sequentially
and starts with person number 1.
He leaves 1, shoots 2, leaves 3, shoots 4 .... and goes on shooting people alternately until only one person remains.
He then offers the lucky man to restart his own kingdom and grants him all his looted resources.
It is you who is asked first to choose your number k. What will you choose as your lucky number?

Input

First line contains T, the number of test cases.
Each test case has the number n in a single line, denoting the number of people captured by Captain Bruno.

Output
For each test case, print the value of k in a single line.

Constraints

1 ≤ T ≤ 100000
1 ≤ n ≤ 1000000000000000000

Example
Input:
6
6
125
32
46
98
156

Output:
5
123
1
29
69
57

Explanation

Case 1: n = 6. In the first round 2, 4, 6 are killed, 1, 3, 5 remain. In next round 3 is killed. Then 1 is killed,
therefore leaving 5. So answer = 5.

见题面

见题面