311118: CF1937A. Shuffle Party

A. Shuffle Partytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$.

Input

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$.

Output

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

ExampleInput

4
1
4
5
120240229

Output

1
4
4
67108864

Note

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$.

题目大意：
题目名为“洗牌派对(A. Shuffle Party)”，在这个问题中，你将会得到一个初始数组，其元素为a1, a2, ..., an，初始时，对于每一个1 ≤ i ≤ n，ai=i。有一个操作swap(k)，对于整数k ≥ 2，定义如下：找到k的最大除数d（d不等于k），然后交换数组中的元素ad和ak。题目要求对每个i=2,3,…,n按顺序执行swap(i)操作，然后找出数字1在结果数组中的位置，即找出j，使得执行这些操作后aj=1。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 接下来的t行，每行包含一个整数n（1 ≤ n ≤ 10^9），表示数组a的长度。

输出：
- 对于每个测试用例，输出执行操作后数字1在数组中的位置。

示例：
输入：
```
4
1
4
5
120240229
```
输出：
```
1
4
4
67108864
```

注意：
- 在第一个测试用例中，数组是[1]，没有执行任何操作。
- 在第二个测试用例中，数组a的变化如下：
- 初始时，a是[1,2,3,4]。
- 执行swap(2)后，a变为[2,1,3,4]。
- 执行swap(3)后，a变为[3,1,2,4]。
- 执行swap(4)后，a变为[3,4,2,1]。
最后，元素1位于索引4（即a4=1）。因此，答案是4。题目大意： 题目名为“洗牌派对(A. Shuffle Party)”，在这个问题中，你将会得到一个初始数组，其元素为a1, a2, ..., an，初始时，对于每一个1 ≤ i ≤ n，ai=i。有一个操作swap(k)，对于整数k ≥ 2，定义如下：找到k的最大除数d（d不等于k），然后交换数组中的元素ad和ak。题目要求对每个i=2,3,…,n按顺序执行swap(i)操作，然后找出数字1在结果数组中的位置，即找出j，使得执行这些操作后aj=1。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 接下来的t行，每行包含一个整数n（1 ≤ n ≤ 10^9），表示数组a的长度。 输出： - 对于每个测试用例，输出执行操作后数字1在数组中的位置。 示例： 输入： ``` 4 1 4 5 120240229 ``` 输出： ``` 1 4 4 67108864 ``` 注意： - 在第一个测试用例中，数组是[1]，没有执行任何操作。 - 在第二个测试用例中，数组a的变化如下： - 初始时，a是[1,2,3,4]。 - 执行swap(2)后，a变为[2,1,3,4]。 - 执行swap(3)后，a变为[3,1,2,4]。 - 执行swap(4)后，a变为[3,4,2,1]。 最后，元素1位于索引4（即a4=1）。因此，答案是4。