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

Дано целое число $$$n$$$.

Определим красоту массива $$$a$$$ как значение выражения $$$|a| - f(a)$$$, где $$$|a|$$$ — длина $$$a$$$, а $$$f(a)$$$ — количество непустых подмассивов$$$^{\text{∗}}$$$ массива $$$a$$$ с побитовым исключающим ИЛИ, равным $$$0$$$. Формально, $$$f(a)$$$ — количество пар $$$(l, r)$$$, для которых $$$1 \le l \le r \le |a|$$$ и $$$a_l \oplus a_{l + 1} \oplus \ldots \oplus a_r = 0$$$$$$^{\text{†}}$$$.

Среди всех массивов $$$a$$$, состоящих из целых чисел от $$$0$$$ до $$$n$$$ и имеющих максимально возможную красоту, найдите массив максимальной длины.

$$$^{\text{∗}}$$$Массив $$$c$$$ является подмассивом массива $$$d$$$, если $$$c$$$ может быть получен из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца. Два подмассива считаются различными, если различаются множества позиций удаленных элементов.

$$$^{\text{†}}$$$$$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

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

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

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

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

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

Для каждого набора входных данных выведите одно целое число $$$k$$$ — длину массива. В следующей строке выведите $$$k$$$ целых чисел $$$a_1, a_2, \ldots, a_k$$$ ($$$0 \le a_i \le n$$$) — элементы массива.

Можно показать, что при данных ограничениях сумма $$$k$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

В первом примере $$$n = 1$$$, поэтому каждый элемент массива равен $$$0$$$ или $$$1$$$. Один из возможных ответов — $$$a = [1, 1, 1]$$$: в нём ровно два подмассива с побитовым исключающим ИЛИ, равным $$$0$$$, а именно $$$(l, r) = (1, 2)$$$ и $$$(l, r) = (2, 3)$$$. Эти два подмассива состоят из одинаковых элементов, но занимают разные позиции, поэтому учитываются оба, и красота $$$a$$$ равна $$$3 - 2 = 1$$$. Можно показать, что в любом массиве длины $$$4$$$ с элементами, равными $$$0$$$ или $$$1$$$, есть хотя бы четыре подмассива с побитовым исключающим ИЛИ, равным $$$0$$$, поэтому его красота не превосходит $$$0$$$.

Во втором примере один из возможных ответов — $$$a = [2, 2, 1, 0, 2, 0, 1]$$$. Его подмассивы с побитовым исключающим ИЛИ, равным $$$0$$$, — это $$$(l, r) = (1, 2)$$$, $$$(2, 7)$$$, $$$(4, 4)$$$ и $$$(6, 6)$$$, поэтому красота $$$a$$$ равна $$$7 - 4 = 3$$$. Массив $$$[1, 2, 2, 1, 2]$$$ также имеет красоту $$$5 - 2 = 3$$$, но он короче. Можно показать, что $$$3$$$ — максимально возможная красота при $$$n = 2$$$, и ни один массив длины больше $$$7$$$ не достигает её.