CFCF2171E.Anisphia Wynn Palettia and Good Permutations

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

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

输入输出样例

输入#1

输出#1

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

首页

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

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

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