Last Number
Description
You are given a multiset $S$. Initially, $S = \{1,2,3, \ldots, n\}$.
You will perform the following operation $n-1$ times.
- Choose the largest number $S_{\text{max}}$ in $S$ and the smallest number $S_{\text{min}}$ in $S$. Remove the two numbers from $S$, and add $S_{\text{max}} - S_{\text{min}}$ into $S$.
It's easy to show that there will be exactly one number left after $n-1$ operations. Output that number.
Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Their description follows.
For each test case, one single line contains a single integer $n$ ($2 \le n \le 10^9$) — the initial size of the multiset $S$.
For each test case, output an integer denoting the only number left after $n-1$ operations.
Input
Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Their description follows.
For each test case, one single line contains a single integer $n$ ($2 \le n \le 10^9$) — the initial size of the multiset $S$.
Output
For each test case, output an integer denoting the only number left after $n-1$ operations.
5
2
4
7
15
177567
1
2
2
4
33914
Note
We show how the multiset $S$ changes for $n=4$.
- Operation $1$: $S=\{1,2,3,4\}$, remove $4$, $1$, add $3$.
- Operation $2$: $S=\{2,3,3\}$, remove $3$, $2$, add $1$.
- Operation $3$: $S=\{1,3\}$, remove $3$, $1$, add $2$.
- Final: $S = \{2\}$.
Thus, the answer for $n = 4$ is $2$.