Задан массив \(a_1, a_2, \ldots, a_n\). Изначально \(a_i=i\) для всех \(1 \le i \le n\).
Для произвольного целого \(k \ge 2\) операция \(\texttt{swap}(k)\) устроена следующим образом:
- Пусть \(d\) — наибольший делитель\(^\dagger\) числа \(k\), не равный \(k\). Тогда нужно поменять местами элементы \(a_d\) и \(a_k\).
Выполним операции \(\texttt{swap}(i)\) для каждого \(i=2,3,\ldots, n\) именно в таком порядке. Найдите позицию, на которой в результате окажется число \(1\). Иными словами, найдите такое \(j\), что \(a_j = 1\) после всех операций.
\(^\dagger\) Целое число \(x\) называется делителем числа \(y\), если существует целое \(z\), для которого \(y = x \cdot z\).
Выходные данные
Для каждого набора входных данных выведите позицию, на которой окажется число \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
4
5
120240229
|
1
4
4
67108864
|