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

Вам дано целое положительное число $$$n$$$.

В этой задаче через $$$\operatorname{MEX}$$$ для набора целых чисел $$$c_1,c_2,\dots,c_k$$$ обозначим наименьшее положительное целое число $$$x$$$, которое не встречается в наборе $$$c$$$.

Простотой массива $$$a_1,\dots,a_n$$$ назовём количество пар $$$(l,r)$$$, таких что $$$1 \le l \le r \le n$$$ и $$$\operatorname{MEX}(a_l,\dots,a_r)$$$ является простым числом.

Найдите произвольную перестановку чисел $$$1,2,\dots,n$$$ с максимально возможным значением простоты среди всех перестановок $$$1,2,\dots,n$$$.

Обратите внимание:

  • Целое число, не меньшее $$$2$$$, называется простым, если его целыми положительными делителями являются только $$$1$$$ и оно само. Например, $$$2,5,13$$$ — простые числа, а $$$1$$$ и $$$6$$$ не простые.
  • Перестановкой чисел $$$1,2,\dots,n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Входные данные

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

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

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

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел, задающих перестановку $$$1,2,\dots,n$$$, на которой достигается максимально возможная простота.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
3
2
1
5
Выходные данные
2 1
1
5 2 1 4 3
Примечание

В первом наборе входных данных есть всего $$$3$$$ пары $$$(l,r)$$$ с $$$1 \le l \le r \le 2$$$, из которых $$$2$$$ имеют простое значение $$$\operatorname{MEX}(a_l,\dots,a_r)$$$:

  • $$$(l,r) = (1,1)$$$: $$$\operatorname{MEX}(2) = 1$$$, что не является простым.
  • $$$(l,r) = (1,2)$$$: $$$\operatorname{MEX}(2,1) = 3$$$, что является простым.
  • $$$(l,r) = (2,2)$$$: $$$\operatorname{MEX}(1) = 2$$$, что является простым.
Отсюда, простота равна $$$2$$$.

Во втором наборе входных данных $$$\operatorname{MEX}(1) = 2$$$ является простым, так что простота равна $$$1$$$.

В третьем наборе входных данных максимально возможная простота равна $$$8$$$.