E. Анисфия Уинн Палеттия и хорошие перестановки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Анис и её новый ассистент Эйфи улучшают метлу ведьмы! Магия требует большой точности и осторожности — чтобы летать, конструкция метлы должна иметь достаточно мало недостатков.

Для произвольного массива $$$a$$$ длины $$$m$$$ индекс $$$i$$$ ($$$1\leq i\leq m-2$$$) называется плохим, если $$$a_i$$$, $$$a_{i+1}$$$ и $$$a_{i+2}$$$ попарно взаимно просты. Более формально, $$$i$$$ является плохим индексом тогда и только тогда, когда $$$\gcd(a_i, a_{i+1}) = \gcd(a_i, a_{i+2}) = \gcd(a_{i+1}, a_{i+2}) = 1$$$$$$^{\text{∗}}$$$. Кроме того, массив $$$a$$$ называется хорошим, если в нём не более $$$6$$$ плохих индексов.

Вам дано целое число $$$n$$$. Постройте хорошую перестановку$$$^{\text{†}}$$$ $$$p$$$ длины $$$n$$$. Можно показать, что такая перестановка всегда существует.

Обратите внимание, что вам не нужно минимизировать количество плохих индексов.

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

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

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

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

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

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

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

Для каждого набора входных данных выведите в одной строке $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$, пример хорошей перестановки длины $$$n$$$.

Если существует несколько подходящих перестановок, вы можете вывести любую из них.

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

Для $$$n=9$$$ мы имеем

$$$i$$$$$$p_i$$$$$$p_{i+1}$$$$$$p_{i+2}$$$$$$\gcd(p_i, p_{i+1})$$$$$$\gcd(p_i, p_{i+2})$$$$$$\gcd(p_{i+1}, p_{i+2})$$$
$$$1$$$$$$5$$$$$$4$$$$$$8$$$$$$1$$$$$$1$$$$$$4$$$
$$$2$$$$$$4$$$$$$8$$$$$$1$$$$$$4$$$$$$1$$$$$$1$$$
$$$3$$$$$$8$$$$$$1$$$$$$9$$$$$$1$$$$$$1$$$$$$1$$$
$$$4$$$$$$1$$$$$$9$$$$$$3$$$$$$1$$$$$$1$$$$$$3$$$
$$$5$$$$$$9$$$$$$3$$$$$$6$$$$$$3$$$$$$3$$$$$$3$$$
$$$6$$$$$$3$$$$$$6$$$$$$2$$$$$$3$$$$$$1$$$$$$2$$$
$$$7$$$$$$6$$$$$$2$$$$$$7$$$$$$2$$$$$$1$$$$$$1$$$

Единственный плохой индекс — $$$3$$$. Поскольку $$$1\leq 6$$$, $$$p$$$ является хорошей перестановкой.