CF1937A.Shuffle Party

You are given an array $a_1, a_2, \ldots, a_n$. Initially, $a_i=i$ for each $1 \le i \le n$.

The operation $\texttt{swap}(k)$ for an integer $k \ge 2$ is defined as follows:

• Let $d$ be the largest divisor$^\dagger$ of $k$ which is not equal to $k$ itself. Then swap the elements $a_d$ and $a_k$.

Suppose you perform $\texttt{swap}(i)$ for each $i=2,3,\ldots, n$ in this exact order. Find the position of $1$ in the resulting array. In other words, find such $j$ that $a_j = 1$ after performing these operations.

$^\dagger$ An integer $x$ is a divisor of $y$ if there exists an integer $z$ such that $y = x \cdot z$.

给你一个数组 $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$ 的最大因子，且不等于 $k$ 本身）。然后交换数组元素 $a_d$ 和 $a_k$。

假设你按顺序依次执行 $\texttt{swap}(i)$，其中 $i = 2, 3, \ldots, n$。求最终数组中元素 $1$ 所在的位置。换言之，求满足 $a_j = 1$ 的下标 $j$。

$^\dagger$ 若存在整数 $z$ 使得 $y = x \cdot z$，则称整数 $x$ 是 $y$ 的一个因子。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains one integer $n$ ($1 \le n \le 10^9$) — the length of the array $a$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$1 \le n \le 10^9$）——即数组 $a$ 的长度。

For each test case, output the position of $1$ in the resulting array.

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

In the first test case, the array is $[1]$ and there are no operations performed.

In the second test case, $a$ changes as follows:

• Initially, $a$ is $[1,2,3,4]$.
• After performing $\texttt{swap}(2)$, $a$ changes to $[\underline{2},\underline{1},3,4]$ (the elements being swapped are underlined).
• After performing $\texttt{swap}(3)$, $a$ changes to $[\underline{3},1,\underline{2},4]$.
• After performing $\texttt{swap}(4)$, $a$ changes to $[3,\underline{4},2,\underline{1}]$.

Finally, the element $1$ lies on index $4$ (that is, $a_4 = 1$). Thus, the answer is $4$.

在第一个测试用例中，数组为 $[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$。