您获得了多重集合 $$$S$$$。最初,$$$S = \{1,2,3, \ldots, n\}$$$。
您将执行以下操作 $$$n-1$$$ 次。
- 选择$$$S$$$中最大的数字$$$S_{\text{max}}$$$和$$$S$$$中最小的数字$$$S_{\text{min}}$$$。删除$$$S$$$中的两个数字,并将$$$S_{\text{max}} - S_{\text{min}}$$$添加到$$$S$$$中。
很容易证明 $$$n-1$$$ 运算后只剩下一个数字。输出那个数字。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。他们的描述如下。
对于每个测试用例,一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^9$$$) — 多重集 $$$S$$$ 的初始大小。
输出
对于每个测试用例,输出一个整数,表示 $$$n-1$$$ 操作后剩下的唯一数字。
示例
输入 #1
5 2 4 7 15 177567
输出 #1
1 2 2 4 33914
注意
我们展示了多重集 $$$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$$$。