A. Перемешиватель
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$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$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$) — длину массива $$$a$$$.

Выходные данные

Для каждого набора входных данных выведите позицию, на которой окажется число $$$1$$$.

Пример
Входные данные
4
1
4
5
120240229
Выходные данные
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$$$.