C. Очередная задача на перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Леше подарили новую игру «НОД-перестановки». Каждый раунд этой игры проходит следующим образом:

  • Сначала Леша выбирает перестановку$$$^{\dagger}$$$ $$$a_1, a_2, \ldots, a_n$$$ целых чисел от $$$1$$$ до $$$n$$$.
  • После этого для всех $$$i$$$ от $$$1$$$ до $$$n$$$ вычисляется целое число $$$d_i = \gcd(a_i, a_{(i \bmod n) + 1})$$$.
  • Счёт раунда равен количеству различных чисел среди $$$d_1, d_2, \ldots, d_n$$$.

Лёша уже сыграл несколько раундов и ему захотелось найти такую перестановку $$$a_1, a_2, \ldots, a_n$$$, что его счёт будет максимально возможным.

Напомним, что $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$, а $$$x \bmod y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$.

$$$^{\dagger}$$$Перестановкой длины $$$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$$$ ($$$2 \le n \le 10^5$$$).

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

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

Для каждого набора входных данных выведите $$$n$$$ различных целых чисел $$$a_{1},a_{2},\ldots,a_{n}$$$ ($$$1 \le a_i \le n$$$) — искомую перестановку.

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

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

В первом наборе входных данных Леше надо найти перестановку чисел от $$$1$$$ до $$$5$$$. Для перестановки $$$a=[1,2,4,3,5]$$$ массив $$$d$$$ равен $$$[1,2,1,1,1]$$$. Он содержит $$$2$$$ различных числа, что является максимумом среди всех перестановок из $$$5$$$ чисел. Существуют и другие ответы для этого набора входных данных.

Во втором наборе входных данных Леше надо найти перестановку чисел от $$$1$$$ до $$$2$$$. Всего существует две такие перестановки — $$$a=[1,2]$$$ и $$$a=[2,1]$$$. В обоих случаях массив $$$d$$$ равен $$$[1,1]$$$, поэтому обе перестановки являются корректным ответом.

В третьем наборе входных данных Леше надо найти перестановку чисел от $$$1$$$ до $$$7$$$. Для перестановки $$$a=[1,2,3,6,4,5,7]$$$ массив $$$d$$$ равен $$$[1,1,3,2,1,1,1]$$$. Он содержит $$$3$$$ различных числа, а значит и счёт раунда с такой перестановкой равен $$$3$$$. Можно показать, что не существует перестановки чисел от $$$1$$$ до $$$7$$$, счёт которой будет больше $$$3$$$.