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 翻译