CF1810H Last 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$ 中恰好只剩下一个数。请输出这个数。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的组数。 接下来每组测试用例一行，包含一个整数 $n$（$2 \le n \le 10^9$），表示多重集 $S$ 的初始大小。

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

以下展示了 $n=4$ 时多重集 $S$ 的变化过程： - 操作 $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$。 由 ChatGPT 4.1 翻译