CF1810H.Last Number

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.

给你一个多重集合 $S$。初始时，$S = \{1,2,3, \ldots, n\}$。

你将执行以下操作 $n-1$ 次：

• 选出 $S$ 中的最大数 $S_{\text{max}}$ 和最小数 $S_{\text{min}}$，将这两个数从 $S$ 中移除，并将 $S_{\text{max}} - S_{\text{min}}$ 加入 $S$。

容易证明，经过 $n-1$ 次操作后，$S$ 中恰好剩下一个数。请输出该数。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。随后是这些测试用例的描述。

对于每个测试用例，一行中包含一个整数 $n$（$2 \le n \le 10^9$），表示多重集 $S$ 的初始大小。

For each test case, output an integer denoting the only number left after $n-1$ operations.

对于每个测试用例，输出一个整数，表示经过 $n-1$ 次操作后剩余的唯一数字。

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$.

我们展示多重集 $S$ 在 $n=4$ 时的变化过程。

• 操作 $1$：$S={1,2,3,4}$，移除 $4$ 和 $1$，添加 $3$。
• 操作 $2$：$S={2,3,3}$，移除 $3$ 和 $2$，添加 $1$。
• 操作 $3$：$S={1,3}$，移除 $3$ 和 $1$，添加 $2$。
• 最终：$S = {2}$。

因此，$n = 4$ 时的答案为 $2$。