题目描述

给定一个数组 $a_1, a_2, \ldots, a_n$，初始时对于每个 $1 \le i \le n$，有 $a_i = i$。

定义操作 $\texttt{swap}(k)$（$k \ge 2$）如下：

• 设 $d$ 为 $k$ 的最大约数（不等于 $k$ 本身）。然后交换 $a_d$ 和 $a_k$ 的值。

假设你依次对每个 $i=2,3,\ldots,n$ 按顺序执行 $\texttt{swap}(i)$ 操作。请你求出最终数组中 $1$ 所在的位置。换句话说，找到满足 $a_j = 1$ 的 $j$。

$^\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]$，没有任何操作。

在第二个测试用例中，$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$。

由 ChatGPT 4.1 翻译

样例

4
1
4
5
120240229

1
4
4
67108864