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

Але досталась сложная задача. К сожалению, она слишком занята баллотированием в студенческий совет. Пожалуйста, решите эту задачу за неё.

Дано целое число $$$n$$$. Постройте перестановку $$$p$$$ целых чисел $$$1, 2, \ldots, n$$$, которая максимизирует значение $$$k$$$ (которое изначально равно $$$0$$$) после следующего процесса.

Выполняется $$$n$$$ операций, на $$$i$$$-й операции ($$$i=1, 2, \dots, n$$$):

  • Если $$$i$$$ нечетно, то $$$k=k\,\&\,p_i$$$, где $$$\&$$$ обозначает операцию побитового И.
  • Если $$$i$$$ четно, то $$$k=k\,|\,p_i$$$, где $$$|$$$ обозначает операцию побитового ИЛИ.
Входные данные

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

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

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

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

Для каждого набора входных данных выведите максимальное значение $$$k$$$ в первой строке и перестановку $$$p_1, p_2,\ldots, p_n$$$ во второй строке.

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

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

В первом наборе входных данных максимальное значение $$$k$$$ получается следующим образом:

Изначально $$$k = 0$$$.

  • На $$$1$$$-й операции: $$$1$$$ нечётно, поэтому Аля задает $$$k$$$ равным $$$k\&p_1 = 0\&2 = 0$$$.
  • На $$$2$$$-й операции: $$$2$$$ чётно, поэтому Аля задает $$$k$$$ равным $$$k|p_2 = 0|1 = 1$$$.
  • На $$$3$$$-й операции: $$$3$$$ нечетно, поэтому Аля задает $$$k$$$ равным $$$k\&p_3 = 1\&3 = 1$$$.
  • На $$$4$$$-й операции: $$$4$$$ четно, поэтому Аля задает $$$k$$$ равным $$$k|p_4 = 1|4 = 5$$$.
  • На $$$5$$$-й операции: $$$5$$$ нечетно, поэтому Аля задает $$$k$$$ равным $$$k\&p_5 = 5\&5 = 5$$$.

Итоговое значение $$$k$$$ равно $$$5$$$. Можно показать, что итоговое значение $$$k$$$ не может превышать $$$5$$$ для всех перестановок длины $$$5$$$. Другой корректный ответ — $$$[2, 3, 1, 4, 5]$$$.

Для второго набора входных данных максимальное значение $$$k$$$ равно $$$7$$$. Можно показать, что итоговое значение $$$k$$$ не может быть больше $$$7$$$ для всех перестановок длины $$$6$$$. Другие корректные ответы: $$$[2, 4, 1, 6, 3, 5]$$$ и $$$[5, 2, 6, 1, 3, 4]$$$.