调用长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$ 好 如果 $$$\gcd(p_i, i)$$$$$$^{\text{†}}$$$ $$$\gt 1$$$ 对于所有 $$$2 \leq i \leq n$$$。找到一个好的排列 最小值 数量 固定点$$$^{\text{‡}}$$$ 涵盖长度 $$$n$$$ 的所有良好排列。如果有多个这样的排列,则打印其中任何一个。
$$$^{\text{*}}$$$ 长度 $$$n$$$ 的排列是一个数组,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数,且顺序任意。
$$$^{\text{†}}$$$$$$\gcd(x, y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。
$$$^{\text{‡}}$$$A 定点 排列 $$$p$$$ 的 是索引 $$$j$$$ ($$$1\leq j\leq n$$$),使得 $$$p_j = j$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 排列的长度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在单行上输出长度 $$$n$$$ 的良好排列示例,其中固定点数量最少。
示例
输入复制
423613
输出复制
1 2 1 2 3 1 4 6 2 5 3 1 12 9 6 10 8 7 4 3 5 11 2 13
注意
在第三个样本中,我们构建了排列
| $$$i$$$ | $$$p_i$$$ | $$$\gcd(p_i, i)$$$ |
| $$$1$$$ | $$$1$$$ | $$$1$$$ |
| $$$2$$$ | $$$4$$$ | $$$2$$$ |
| $$$3$$$ | $$$6$$$ | $$$3$$$ |
| $$$4$$$ | $$$2$$$ | $$$2$$$ |
| $$$5$$$ | $$$5$$$ | $$$5$$$ |
| $$$6$$$ | $$$3$$$ | $$$3$$$ |