Problem A
Alchemy 101
As a student at Hogwarts School of Witchcraft and Wizardry, Harry must learn Alchemy — the study of magical properties of elements and transmutation of substances. In today’s Alchemy lab session, Harry is experimenting with transmuting substances. In the magical world, there are infinite number of substances, numbered by positive integers. When combining two substances $i$ and $j$, one will obtain the substance $i \oplus j$, where $\oplus $ denote the bitwise xor operator.
Let’s take a recap of how the bitwise xor operator works. The bitwise xor is a binary operation that takes two bit sequences of equal length and performs the logical exclusive or operation on each pair of corresponding bits. The result in each position is $1$ if only one of the bits is $1$, but will be $0$ if both are $0$s or both are $1$s. For example:
|
0 |
1 |
0 |
1 |
(decimal $5$) |
|||
|
XOR |
0 |
0 |
1 |
1 |
(decimal $3$) |
||
|
0 |
1 |
1 |
0 |
(decimal $6$) |
Thus, we can write $5 \oplus 3 = 6$. For this problem, we can say by combining substances $5$ and $3$, one will get substance $5 \oplus 3 = 6$. Note that, the order of combining substances does not matter, because of the commutativity and associativity properties of the bitwise xor operator:
-
$a \oplus b = b \oplus a$,
-
$a \oplus (b \oplus c) = (a \oplus b) \oplus c$.
Harry wants to create the substance $m$, using the largest number of substances. However, Hogwarts’ lab only has $m$ substances from $1$ to $m$, so Harry can only use these substances and he can not use any substances twice.
Input
The first line of the input contains a single integer $t$ $(1 \le t \le 10^{3})$ — the number of test cases.
$t$ test cases follow, each test case contains a single integer $m$ $(1 \le m \le 10^{3})$. It is guaranteed that one can create the substance $m$, using only substances numbered from $1$ to $m$ without using any substances more than once.
Output
For each test case, print two lines:
-
The first line contains $n$ — the largest number of substances Harry can use.
-
The second line contains $n$ integers, separated by spaces — the substances that Harry uses.
If there are more than one optimal answers, you must print the one with smallest lexicographical order. A list of substances $a_1, a_2, \ldots , a_ n$ has smaller lexicographical order than a list of substances $b_1, b_2, \ldots , b_ n$, iff there exists a valid index $i$ such that both the following conditions are true:
-
$a_1 = b_1, a_2 = b_2, \ldots , a_{i-1} = b_{i-1}$,
-
$a_ i < b_ i$.
Explanation of the sample input
-
$1 = 1$,
-
$1 \oplus 2 \oplus 3 \oplus 4 = 4$,
-
$1 \oplus 2 \oplus 3 \oplus 5 = 5$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 4 5 |
1 1 4 1 2 3 4 4 1 2 3 5 |
