题目描述

又一个排列问题

Alex 收到了一个名为 "GCD 排列" 的游戏作为生日礼物。这个游戏的每一轮进行如下操作：

• 首先，Alex 选择一个整数序列 $^{\dagger}$ $a_1, a_2, \ldots, a_n$ ，其中整数范围从 $1$ 到 $n$ 。
• 然后，对于每个 $i$ 从 $1$ 到 $n$ ，计算整数 $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$ 的排列是一个由 $n$ 个不同整数组成的数组，整数范围从 $1$ 到 $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

样例输入 #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$ 组成的排列中没有得分更高的。

样例

4
5
2
7
10

1 2 4 3 5 
1 2 
1 2 3 6 4 5 7 
1 2 3 4 8 5 10 6 9 7