H. Xor and Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$.

Construct a permutation $$$p_0, p_1, \ldots, p_{n-1}$$$ of the integers $$$\{0,1,\ldots,n-1\}$$$, such that $$$$$$f(p)=\sum_{i=0}^{n-2} (p_i \oplus p_{i+1})$$$$$$ is minimum possible.

Here, $$$\oplus$$$ denotes the bitwise XOR operation (https://en.wikipedia.org/wiki/Bitwise_operation#XOR)

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 500)$$$, representing the number of test cases.

Each of the next $$$t$$$ lines contains a single integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$, which denotes the size of the permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single line containing the permutation $$$p$$$ of $$$\{0, 1, \dots, n-1\}$$$ such that $$$f(p)=\sum_{i=0}^{n-2} (p_i \oplus p_{i+1})$$$ is minimum possible.

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

In the first test case, $$$f(p)=0 \oplus 1=1$$$, which is the minimum possible. Another valid permutation is $$$p=[0,1]$$$.

In the second test case, $$$f(p)=(3 \oplus 2)+(2 \oplus 0)+(0 \oplus 1)=1+2+1=4$$$, which is the minimum possible. Other valid permutations, such as $$$p=[0,1,3,2]$$$, also exist.