B. Strange Shuffle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a big array $$$a$$$ of size $$$n$$$ and $$$a_i=i$$$ initially.

The following process will be repeated cyclically until there is only one element left:

  1. Erase $$$a_1$$$.
  2. Note $$$x$$$ is the amount of elements in the current $$$a$$$.Move the first $$$⌊x/2 ⌋$$$ elements after the last $$$x-⌊x/2 ⌋$$$ elements.
  3. Erase $$$a_1$$$.
  4. Reverse the whole array.

Find the value of the last remaining element.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of a line of input.The only line of each test case contains an integer $$$n(1 \leq n \leq 10^{18})$$$.

Output

For each test case, output on a new line — the value of the last remaining element.

Example
Input
5
1
4
5
101
12345678910
Output
1
4
2
26
9259259183
Note

Test case $$$1$$$:There're only one element $$$1$$$.So the answer is $$$1$$$.

Test case $$$2$$$:$$$[1,2,3,4]→[2,3,4]→[3,4,2]→[4,2]→[2,4]→[4]$$$.

Test case $$$3$$$:$$$[1,2,3,4,5]→[2,3,4,5]→[4,5,2,3]→[5,2,3]→[3,2,5]→[2,5]→[5,2]→[2]$$$.