No submission language available for this problem.

Description

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains one integer $n$ ($1 \le n \le 10^9$) — the length of the array $a$.

Output

For each test case, output the position of $1$ in the resulting array.

4
1
4
5
120240229
 
 

1
4
4
67108864

Note

In the first test case, the array is $[1]$ and there are no operations performed.

In the second test case, $a$ changes as follows:

• Initially, $a$ is $[1,2,3,4]$.
• After performing $\texttt{swap}(2)$, $a$ changes to $[\underline{2},\underline{1},3,4]$ (the elements being swapped are underlined).
• After performing $\texttt{swap}(3)$, $a$ changes to $[\underline{3},1,\underline{2},4]$.
• After performing $\texttt{swap}(4)$, $a$ changes to $[3,\underline{4},2,\underline{1}]$.

Finally, the element $1$ lies on index $4$ (that is, $a_4 = 1$). Thus, the answer is $4$.