题目描述

我一直很喜欢“魔法”这个词。它能让人快乐，让人露出微笑。

——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$ 的好排列。若有多个解，可输出任意一个。

样例

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$，例如：

唯一的坏下标是 $3$。因为 $1 \leq 6$，所以 $p$ 是一个好排列。

由 ChatGPT 5 翻译

来源

Codeforces 2171E，英文题名 Anisphia Wynn Palettia and Good Permutations。