← 返回题目列表

Codeforces · 1937/A

A. 洗牌派对

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

给你一个数组 $$$a_1, a_2, \ldots, a_n$$$。最初,对于每个 $$$1 \le i \le n$$$,$$$a_i=i$$$。

整数 $$$k \ge 2$$$ 的运算 $$$\texttt{swap}(k)$$$ 定义如下:

- 让 $$$d$$$ 为 $$$k$$$ 的最大除数 $$$^\dagger$$$,它不等于 $$$k$$$ 本身。然后交换元素$$$a_d$$$ 和$$$a_k$$$。

假设您按此确切顺序对每个 $$$i=2,3,\ldots, n$$$ 执行 $$$\texttt{swap}(i)$$$。查找结果数组中 $$$1$$$ 的位置。换句话说,执行这些操作后,找到这样的$$$j$$$,使得$$$a_j = 1$$$。

$$$^\dagger$$$ 如果存在一个整数 $$$z$$$ 使得 $$$y = x \cdot z$$$,则整数 $$$x$$$ 是 $$$y$$$ 的除数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^9$$$) — 数组 $$$a$$$ 的长度。

输出

对于每个测试用例,输出 $$$1$$$ 在结果数组中的位置。

示例

输入 #1

4
1
4
5
120240229

输出 #1

1
4
4
67108864

注意

在第一个测试用例中,数组是 $$$[1]$$$ 并且没有执行任何操作。

在第二个测试用例中,$$$a$$$ 更改如下:

- 最初,$$$a$$$ 是$$$[1,2,3,4]$$$。
- 执行 $$$\texttt{swap}(2)$$$ 后,$$$a$$$ 更改为 $$$[\underline{2},\underline{1},3,4]$$$ (被交换的元素带有下划线)。
- 执行 $$$\texttt{swap}(3)$$$ 后,$$$a$$$ 更改为 $$$[\underline{3},1,\underline{2},4]$$$。
- 执行 $$$\texttt{swap}(4)$$$ 后,$$$a$$$ 更改为 $$$[3,\underline{4},2,\underline{1}]$$$。

最后,元素 $$$1$$$ 位于索引 $$$4$$$ 上(即 $$$a_4 = 1$$$)。因此,答案是$$$4$$$。