← 返回题目列表

Codeforces · 2171/E

E. Anisphia Wynn Palettia 和良好的排列

中文机器翻译题面 查看原题
我一直很喜欢魔法这个词。它有一种让人们快乐、让人们脸上露出微笑的方式。
— Anisphia Wynn Palettia

阿尼斯和她的新助手尤菲正在改进女巫的扫帚!魔法学需要高度的精确性和细心——为了飞行,扫帚的结构必须有足够少的缺陷。

对于长度为 $$$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$$$ 的良好排列示例。如果有多个好的排列,则可以输出其中任何一个。

示例

输入
复制

4
3
6
8
9

输出
复制

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$$$ 是一个很好的排列。