F. Минимизировать неподвижные точки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем перестановку$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$ хорошей, если $$$\gcd(p_i, i)$$$$$$^{\text{†}}$$$ $$$ \gt 1$$$ для всех $$$2 \leq i \leq n$$$. Найдите хорошую перестановку с минимальным количеством неподвижных точек$$$^{\text{‡}}$$$ среди всех хороших перестановок длины $$$n$$$. Если таких перестановок несколько, выведите любую из них.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ — это массив, который содержит каждое целое число от $$$1$$$ до $$$n$$$ ровно один раз, в любом порядке.

$$$^{\text{†}}$$$$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) $$$x$$$ и $$$y$$$.

$$$^{\text{‡}}$$$Неподвижная точка перестановки $$$p$$$ — это индекс $$$j$$$ ($$$1\leq j\leq n$$$), такой что $$$p_j = j$$$.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — длину перестановки.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных выведите на одной строке хорошую перестановку длины $$$n$$$ с минимальным количеством неподвижных точек.

Пример
Входные данные
4
2
3
6
13
Выходные данные
1 2
1 2 3
1 4 6 2 5 3
1 12 9 6 10 8 7 4 3 5 11 2 13
Примечание

В третьем примере мы строим перестановку

$$$i$$$$$$p_i$$$$$$\gcd(p_i, i)$$$
$$$1$$$$$$1$$$$$$1$$$
$$$2$$$$$$4$$$$$$2$$$
$$$3$$$$$$6$$$$$$3$$$
$$$4$$$$$$2$$$$$$2$$$
$$$5$$$$$$5$$$$$$5$$$
$$$6$$$$$$3$$$$$$3$$$
Тогда мы видим, что $$$\gcd(p_i, i) \gt 1$$$ для всех $$$2\leq i\leq 6$$$. Более того, мы видим, что есть только две неподвижные точки, а именно $$$1$$$ и $$$5$$$. Можно показать, что невозможно построить хорошую перестановку длины $$$6$$$ с меньшим количеством неподвижных точек.