← 返回题目列表

Codeforces · 1810/H

H. 最后一个号码

中文机器翻译题面 查看原题

您获得了多重集合 $$$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$$$。