最终决定在 179 学校的足球场上建造一个屋顶。其建造需要放置 $$$n$$$ 连续的垂直柱子。此外,校长希望所有柱子的高度形成从 $$$0$$$ 到 $$$n - 1$$$ 的整数排列 $$$p$$$,其中 $$$p_i$$$ 是从左边开始第 $$$i$$$ 柱子的高度 $$$(1 \le i \le n)$$$。
作为酋长,您知道建造连续柱子的成本等于所有相邻柱子对的高度按位异或的最大值。换句话说,构造成本等于 $$$\max\limits_{1 \le i \le n - 1}{p_i \oplus p_{i + 1}}$$$,其中 $$$\oplus$$$ 表示按位异或运算。
找出任意长度为 $$$n$$$ 且建造成本最小的柱子高度 $$$p$$$ 的序列。
在此问题中,排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$0$$$ 到 $$$n - 1$$$ 的任意顺序。例如,$$$[2,3,1,0,4]$$$ 是一个排列,但 $$$[1,0,1]$$$ 不是排列($$$1$$$ 在数组中出现两次),$$$[1,0,3]$$$ 也不是排列($$$n=3$$$,但 $$$3$$$ 在数组中)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 用于建造屋顶的柱子数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数 $$$p_1$$$、$$$p_2$$$、$$$\ldots$$$、$$$p_n$$$ — 具有最小建造成本的支柱高度序列。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
4 2 3 5 10
输出 #1
0 1 2 0 1 3 2 1 0 4 4 6 3 2 0 8 9 1 7 5
注意
对于 $$$n = 2$$$,有 $$$2$$$ 柱高度序列:
- $$$[0, 1]$$$ — 建造成本为 $$$0 \oplus 1 = 1$$$。
- $$$[1, 0]$$$ — 建造成本为 $$$1 \oplus 0 = 1$$$。
对于 $$$n = 3$$$,有 $$$6$$$ 柱子高度序列:
- $$$[0, 1, 2]$$$ — 建造成本为 $$$\max(0 \oplus 1, 1 \oplus 2) = \max(1, 3) = 3$$$。
- $$$[0, 2, 1]$$$ — 建造成本为 $$$\max(0 \oplus 2, 2 \oplus 1) = \max(2, 3) = 3$$$。
- $$$[1, 0, 2]$$$ — 建造成本为 $$$\max(1 \oplus 0, 0 \oplus 2) = \max(1, 2) = 2$$$。
- $$$[1, 2, 0]$$$ — 建造成本为 $$$\max(1 \oplus 2, 2 \oplus 0) = \max(3, 2) = 3$$$。
- $$$[2, 0, 1]$$$ — 建造成本为 $$$\max(2 \oplus 0, 0 \oplus 1) = \max(2, 1) = 2$$$。
- $$$[2, 1, 0]$$$ — 建造成本为 $$$\max(2 \oplus 1, 1 \oplus 0) = \max(3, 1) = 3$$$。