Description

Farmer LHR has n LMRs. There is no doubt that LMRs like best.

In order to avoid the crowding during the meal, the clever LHR comes up with a meal order to ensure that only one LMR has dinner at the same time.

The meal order is as follows:

There are n LMRs in a circle numbered from 1 to n clockwise.

Starting counting from the LMR numbered 1, the second LMR counted leaves to eat grass and doesn't come back anymore.

Then, starting counting from the next LMR, the second LMR counted leaves to eat grass and doesn't come back anymore. This process will continue until there is only one LMR left.

Now, LHR wants to know which LMR will be the last one, can you help her?

Format

Input

The first line is an integer $T(1\le T\le 10)$ indicating the test cases.

Followed by T line, each line has an integer $n(2\le n\le 10^9)$ indicating the number of LMRs.

Output

Output T lines, each line has an integer indicating the number of LMR which is the last one.

Samples

2
2
5

1
3

Hints

when $n=2$ At first, the sequence of LMRs is$[1-2-1]$. Then the LMR numbered 2 leave to eat grass, the sequence of LMRs becomes $[1 - 1]$. when $n=5$ At first,the sequence of LMRs is $[1 - 2 -3-4-5- 1]$ Then the LMR numbered 2 leave to eatgrass,the sequence ofLMRs becomes $[1 -3-4-5- 1]$ Then the LMR numbered 4 leave to eat arass, the sequence ofLMRs becomes $[1-3-5-1]$ Then the LMR numbered 1 leave to eat grass, the sequence ofLMRs becomes $[3-5-3]$ Then the LMR numbered 5 leave to eat grass, the sequence of LMRs becomes $[3 - 3]$. Therefore, the LMR numbered 3 is the last one.