CF2123F.Minimize Fixed Points

称一个长度为 $n$ 的排列 $p$ 是“好”的，如果对于所有 $2 \leq i \leq n$，都有 $\gcd(p_i, i) > 1$。请你在所有长度为 $n$ 的“好”排列中，找到一个定点数最少的“好”排列。如果有多个这样的排列，输出任意一个即可。

一个长度为 $n$ 的排列是一个数组，包含了 $1$ 到 $n$ 的所有整数，且每个整数恰好出现一次，顺序任意。

$\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。

排列 $p$ 的定点是指满足 $p_j = j$ 的下标 $j$（$1 \leq j \leq n$）。

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

每个测试用例包含一行，一个整数 $n$（$2 \leq n \leq 10^5$），表示排列的长度。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一行，给出一个长度为 $n$ 的“好”排列，且定点数最少。若有多个答案，输出任意一个即可。

在第三个样例中，我们构造的排列如下：

$i$	$p_i$	$\gcd(p_i, i)$
$1$	$1$	$1$
$2$	$4$	$2$
$3$	$6$	$3$
$4$	$2$	$2$
$5$	$5$	$5$
$6$	$3$	$3$

可以看到，对于所有 $2 \leq i \leq 6$，都有 $\gcd(p_i, i) > 1$。此外，只有 $1$ 和 $5$ 是定点。可以证明，无法构造出定点更少的长度为 $6$ 的“好”排列。

由 ChatGPT 4.1 翻译