Alex 收到了一款名为“GCD 排列”的新游戏作为生日礼物。本游戏每轮进行如下:
- 首先,Alex 选择从 $$$1$$$ 到 $$$n$$$ 的整数排列$$$^{\dagger}$$$ $$$a_1, a_2, \ldots, a_n$$$。
- 然后,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,计算一个整数 $$$d_i = \gcd(a_i, a_{(i \bmod n) + 1})$$$。
- 该轮的分数是 $$$d_1, d_2, \ldots, d_n$$$ 中不同数字的数量。
Alex 已经玩了几轮,所以他决定找到一个排列 $$$a_1, a_2, \ldots, a_n$$$ ,使其分数尽可能大。
回想一下, $$$\gcd(x, y)$$$ 表示数字 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD),$$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 的余数。
$$$^{\dagger}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由一行组成,其中包含单个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 不同的整数 $$$a_{1},a_{2},\ldots,a_{n}$$$ ($$$1 \le a_i \le n$$$) - 具有最大可能得分的排列。
如果存在多个具有最大可能得分的排列,您可以打印其中任何一个。
示例
输入 #1
4 5 2 7 10
输出 #1
1 2 4 3 5 1 2 1 2 3 6 4 5 7 1 2 3 4 8 5 10 6 9 7
注意
在第一个测试用例中,Alex 想要找到从 $$$1$$$ 到 $$$5$$$ 的整数排列。对于排列 $$$a=[1,2,4,3,5]$$$,数组 $$$d$$$ 等于 $$$[1,2,1,1,1]$$$。它包含 $$$2$$$ 不同的整数。可以证明,不存在长度$$$5$$$得分更高的排列。
在第二个测试用例中,Alex 想要找到从 $$$1$$$ 到 $$$2$$$ 的整数排列。这样的排列只有两种:$$$a=[1,2]$$$ 和 $$$a=[2,1]$$$。在这两种情况下,数组 $$$d$$$ 等于 $$$[1,1]$$$,因此两种排列都是正确的。
在第三个测试用例中,Alex 想要找到从 $$$1$$$ 到 $$$7$$$ 的整数排列。对于排列 $$$a=[1,2,3,6,4,5,7]$$$,数组 $$$d$$$ 等于 $$$[1,1,3,2,1,1,1]$$$。它包含 $$$3$$$ 不同的整数,因此其得分等于 $$$3$$$。可以证明,从 $$$1$$$ 到 $$$7$$$ 之间不存在得分高于 $$$3$$$ 的整数排列。