G. Be Positive
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Find the lexicographically smallest permutation $$$p_0, p_1, p_2 \cdots, p_{n-1}$$$ of $$$0, 1, 2, \cdots, (n - 1)$$$ satisfying the following constraint: For all $$$0 \le i \lt n$$$, $$$p_0 \oplus p_1 \oplus \cdots \oplus p_i \gt 0$$$. Here $$$\oplus$$$ is the bitwise exclusive or operation.

We say an integer sequence $$$p_0, p_1, \cdots, p_{n - 1}$$$ of length $$$n$$$ is lexicographically smaller than another integer sequence $$$q_0, q_1, \cdots, q_{n - 1}$$$ of length $$$n$$$, if there exists an integer $$$0 \le k \lt n$$$ such that $$$p_i = q_i$$$ for all $$$0 \le i \lt k$$$ and $$$p_k \lt q_k$$$.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first and only line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

It's guaranteed that the sum of $$$n$$$ of all test cases does not exceed $$$10^6$$$.

Output

For each test case output one line containing $$$n$$$ integers separated by a space, indicating the lexicographically smallest permutation satisfying the constraint. If there is no such permutation, output impossible instead.

Example
Input
4
1
2
3
4
Output
impossible
1 0
1 0 2
impossible