CF2171E Anisphia Wynn Palettia and Good Permutations

我一直很喜欢“魔法”这个词。它能让人快乐，让人露出微笑。 ——Anisphia Wynn Palettia Anis 和她的新助手 Euphie 正在改进女巫的扫帚！魔法学需要极高的精度和谨慎——为了让扫帚飞起来，扫帚的构造中必须尽可能少有瑕疵。 对于任意长度为 $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$ 时，$i$ 是坏下标。此外，如果一个数组 $a$ 的坏下标不超过 $6$ 个，则称 $a$ 是好数组。 现在给定一个整数 $n$，请构造一个长度为 $n$ 的好排列 $p$。可以证明一定存在这样的排列。 注意，你无需最小化坏下标的个数。 $\gcd(x, y)$ 表示 $x$ 与 $y$ 的最大公约数。 排列定义为从 $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, \ldots, p_n$，表示一个长度为 $n$ 的好排列。若有多个解，可输出任意一个。

对于 $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$ 是一个好排列。 由 ChatGPT 5 翻译