Problem Description

Maddy encountered a machine. In front of the machine, she needs to report a long sequence of numbers so that she can obtain the Crystal Heart.
The machine first tells Maddy an integer $n$. Specifically, the sequence must satisfy the following:

1. The sequence consists of $n$ integers within $[0, 2^{30})$, denoted as $a_1, a_2, \dots, a_n$.
2. For all $1 \le i < n$, it holds that $a_i < a_{i+1}$ and $a_i \text{ xor } a_{i+1} < a_i \text{ and } a_{i+1}$.

Please help Maddy find such a sequence, or tell Maddy that no solution exists.

Input Format

The first line contains an integer $T$ ($1 \le T \le 10^3$), representing the number of testdata.
The only line of each testdata contains an integer $n$ ($2 \le n \le 10^6$), representing the number given by the machine to Maddy.
It is guaranteed that $\sum n \le 10^6$ over all testdata.

Output Format

For each testdata, if such a sequence exists, output one line with $n$ integers representing a sequence that satisfies the machine’s requirements. If it does not exist, output a single integer $-1$ in one line.
If there are multiple valid answers, you may output any one of them.

4
2
3
4
5

9 15
4 5 6
9 10 12 15
8 9 10 11 12

Hint

Sample 1 Explanation

For the 1st sample, $a_1 \text{ xor } a_2 = 9 \text{ xor } 15 = 6$, and $a_1 \text{ and } a_2 = 9 \text{ and } 15 = 9$, so $a_1 \text{ xor } a_2 < a_1 \text{ and } a_2$. It is also easy to see that $a_1 < a_2$.
For the 2nd sample,

• $a_1 \text{ xor } a_2 = 4 \text{ xor } 5 = 1$, and $a_1 \text{ and } a_2 = 4 \text{ and } 5 = 4$, so $a_1 \text{ xor } a_2 < a_1 \text{ and } a_2$. It is also easy to see that $a_1 < a_2$.
• $a_2 \text{ xor } a_3 = 5 \text{ xor } 6 = 3$, and $a_2 \text{ and } a_3 = 5 \text{ and } 6 = 4$, so $a_2 \text{ xor } a_3 < a_2 \text{ and } a_3$. It is also easy to see that $a_2 < a_3$.

Hint

For two integers $a$ and $b$, $a \text{ xor } b$ denotes the bitwise XOR, meaning a bit in the binary representation of the result is 1 if and only if in the binary representations of the original numbers, exactly one of them has a 1 at that bit.
For two integers $a$ and $b$, $a \text{ and } b$ denotes the bitwise AND, meaning a bit in the binary representation of the result is 1 if and only if in the binary representations of the original numbers, both have a 1 at that bit.

Translated by ChatGPT 5