阿尼斯和她的新助手尤菲正在改进女巫的扫帚!魔法学需要高度的精确性和细心——为了飞行,扫帚的结构必须有足够少的缺陷。
对于长度为 $$$m$$$ 的任意数组 $$$a$$$,调用索引 $$$i$$$ ($$$1\leq i\leq m-2$$$) 坏 如果 $$$a_i$$$、$$$a_{i+1}$$$ 和 $$$a_{i+2}$$$ 都是成对互质。更正式地说,$$$i$$$ 是一个坏索引当且仅当 $$$\gcd(a_i, a_{i+1}) = \gcd(a_i, a_{i+2}) = \gcd(a_{i+1}, a_{i+2}) = 1$$$$$$^{\text{*}}$$$。此外,请致电 $$$a$$$ 好 如果它最多有 $$$6$$$ 坏索引。
给你一个整数$$$n$$$。构建一个长度为 $$$n$$$ 的良好排列$$$^{\text{†}}$$$ $$$p$$$。可以证明这样的排列总是存在的。
请注意,您不必最小化坏索引的数量。
$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最大公约数
$$$^{\text{†}}$$$ 长度 $$$n$$$ 的排列是一个数组,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数,且顺序任意。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$3\leq n \leq 2\cdot 10^5$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,在单行上输出 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$,长度 $$$n$$$ 的良好排列示例。如果有多个好的排列,则可以输出其中任何一个。
示例
输入复制
43689
输出复制
2 1 3 4 1 6 3 5 2 4 1 6 3 5 2 8 7 5 4 8 1 9 3 6 2 7
注意
对于 $$$n=9$$$,我们有
| $$$i$$$ | $$$p_i$$$ | $$$p_{i+1}$$$ | $$$p_{i+2}$$$ | $$$\gcd(p_i, p_{i+1})$$$ | $$$\gcd(p_i, p_{i+2})$$$ | $$$\gcd(p_{i+1}, p_{i+2})$$$ |
| $$$1$$$ | $$$5$$$ | $$$4$$$ | $$$8$$$ | $$$1$$$ | $$$1$$$ | $$$4$$$ |
| $$$2$$$ | $$$4$$$ | $$$8$$$ | $$$1$$$ | $$$4$$$ | $$$1$$$ | $$$1$$$ |
| $$$3$$$ | $$$8$$$ | $$$1$$$ | $$$9$$$ | $$$1$$$ | $$$1$$$ | $$$1$$$ |
| $$$4$$$ | $$$1$$$ | $$$9$$$ | $$$3$$$ | $$$1$$$ | $$$1$$$ | $$$3$$$ |
| $$$5$$$ | $$$9$$$ | $$$3$$$ | $$$6$$$ | $$$3$$$ | $$$3$$$ | $$$3$$$ |
| $$$6$$$ | $$$3$$$ | $$$6$$$ | $$$2$$$ | $$$3$$$ | $$$1$$$ | $$$2$$$ |
| $$$7$$$ | $$$6$$$ | $$$2$$$ | $$$7$$$ | $$$2$$$ | $$$1$$$ | $$$1$$$ |
唯一不好的索引是$$$3$$$。由于 $$$1\leq 6$$$,$$$p$$$ 是一个很好的排列。