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

В 179-й школе наконец решили построить крышу над полем для игры в футбол. Уже известно, что для строительства потребуется последовательно поставить $$$n$$$ вертикальных опор. При этом директор школы хочет, чтобы высоты всех опор образовывали перестановку $$$p$$$ чисел от $$$0$$$ до $$$n - 1$$$, где $$$p_i$$$ — высота $$$i$$$-й слева опоры $$$(1 \le i \le n)$$$.

Вам, как заведующему строительством, известно, что стоимость постройки последовательности опор определяется как максимальное значение побитового исключающего ИЛИ высот всех пар соседних опор. Иными словами, стоимость постройки равна $$$\max\limits_{1 \le i \le n - 1}{p_i \oplus p_{i + 1}}$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Найдите любую последовательность из высот опор $$$p$$$ длины $$$n$$$, стоимость постройки которой минимальна.

Здесь перестановкой является массив, состоящий из $$$n$$$ различных целых чисел от $$$0$$$ до $$$n - 1$$$ в произвольном порядке. Например, $$$[2,3,1,0,4]$$$ — перестановка, но $$$[1,0,1]$$$ не перестановка ($$$1$$$ встречается в массиве дважды) и $$$[1,0,3]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$3$$$).

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

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

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

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

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

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

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

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

Для $$$n = 2$$$ есть $$$2$$$ возможные последовательности высот опор:

  • $$$[0, 1]$$$ — цена постройки равна $$$0 \oplus 1 = 1$$$.
  • $$$[1, 0]$$$ — цена постройки равна $$$1 \oplus 0 = 1$$$.

Для $$$n = 3$$$ есть $$$6$$$ возможных последовательностей высот опор:

  • $$$[0, 1, 2]$$$ — цена постройки равна $$$\max(0 \oplus 1, 1 \oplus 2) = \max(1, 3) = 3$$$.
  • $$$[0, 2, 1]$$$ — цена постройки равна $$$\max(0 \oplus 2, 2 \oplus 1) = \max(2, 3) = 3$$$.
  • $$$[1, 0, 2]$$$ — цена постройки равна $$$\max(1 \oplus 0, 0 \oplus 2) = \max(1, 2) = 2$$$.
  • $$$[1, 2, 0]$$$ — цена постройки равна $$$\max(1 \oplus 2, 2 \oplus 0) = \max(3, 2) = 3$$$.
  • $$$[2, 0, 1]$$$ — цена постройки равна $$$\max(2 \oplus 0, 0 \oplus 1) = \max(2, 1) = 2$$$.
  • $$$[2, 1, 0]$$$ — цена постройки равна $$$\max(2 \oplus 1, 1 \oplus 0) = \max(3, 1) = 3$$$.