CF2171E.Anisphia Wynn Palettia and Good Permutations

I've always loved the word magic. It has a way of making people happy, of putting a smile on their faces.

— Anisphia Wynn Palettia

Anis and her new assistant Euphie are improving the Witch's Broom! Magicology requires great precision and care — in order to fly, the construction of the broom must have sufficiently few imperfections.

For an arbitrary array $a$ of length $m$, call an index $i$ ($1\leq i\leq m-2$) bad if $a_i$, $a_{i+1}$, and $a_{i+2}$ are all pairwise coprime. More formally, $i$ is a bad index if and only if $\gcd(a_i, a_{i+1}) = \gcd(a_i, a_{i+2}) = \gcd(a_{i+1}, a_{i+2}) = 1$$^{\text{∗}}$. Furthermore, call $a$ good if it has at most $6$ bad indices.

You are given an integer $n$. Construct a good permutation$^{\text{†}}$ $p$ of length $n$. It can be shown that such a permutation always exists.

Note that you do not have to minimize the number of bad indices.

$^{\text{∗}}$$\gcd(x, y)$ denotes the greatest common divisor of $x$ and $y$

$^{\text{†}}$ A permutation of length $n$ is an array that contains every integer from $1$ to $n$ exactly once, in any order.

我一向钟爱“魔法”这个词。它总能给人带来快乐，让人脸上绽放笑容。

——阿尼丝菲娅·温·帕莱提亚

阿尼丝与她的新助手尤菲正着手改进女巫的扫帚！魔法学要求极高的精确性与细致程度——为了使扫帚能够飞行，其构造必须具有足够少的缺陷。

对于任意长度为 $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$ 的每个整数恰好一次的数组（顺序任意）。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The only line of each test case contains a single integer $n$ ($3\leq n \leq 2\cdot 10^5$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。

每个测试用例仅有一行，包含一个整数 $n$（$3\leq n \leq 2\cdot 10^5$）。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

For each test case, output on a single line $n$ integers $p_1, p_2, \dots, p_n$, an example of a good permutation of length $n$. If there are multiple good permutations, you may output any of them.

对于每个测试用例，在一行中输出 $n$ 个整数 $p_1, p_2, \dots, p_n$，即一个长度为 $n$ 的好排列的例子。如果存在多个好排列，你可以输出其中任意一个。

For $n=9$, we have

$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$

The only bad index is $3$. Since $1\leq 6$, $p$ is a good permutation.

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