C. 最小异或乘积
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

请你构造一个 $$$0$$$ 到 $$$n-1$$$ 的排列 $$$a$$$，以最小化相邻元素的异或值之积，即最小化以下表达式： $$$$$$\prod_{i=1}^{n-1} (a_i \oplus a_{i+1})$$$$$$ 如果有多个序列满足条件，请输出字典序最小的那个。

Input

第一行输入一个整数 $$$t$$$ $$$(1 \le t \le 10^3)$$$，表示测试用例的数量。

接下来 $$$t$$$ 行，每行输入一个整数 $$$n$$$ $$$(1 \le n \le 2 \times 10^6)$$$，表示排列的长度。

保证所有测试用例中 $$$n$$$ 的总和不超过 $$$2 \times 10^6$$$。

Output

对于每个测试用例，输出一行 $$$n$$$ 个整数，表示满足条件的排列。

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

对于第二组样例，排列 $$$0,1,3,2$$$ 的相邻异或值分别为 $$$0 \oplus 1 = 1$$$、$$$1 \oplus 3 = 2$$$、$$$3 \oplus 2 = 1$$$， 因此乘积为 $$$1 \times 2 \times 1 = 2$$$。 可以证明不存在乘积更小的排列。