题目描述

给定一个正整数 $n$。

在本题中，集合 $c_1, c_2, \dots, c_k$ 的 $\operatorname{MEX}$ 被定义为不在集合 $c$ 中出现的最小正整数 $x$。

一个数组 $a_1, \dots, a_n$ 的“素性”被定义为满足 $1 \le l \le r \le n$ 且 $\operatorname{MEX}(a_l, \dots, a_r)$ 为素数的所有区间对 $(l, r)$ 的数量。

请你在所有 $1,2,\dots,n$ 的排列中，找出一种“素性”最大的排列，并输出任意一种。

注意：

• 素数是大于等于 $2$ 且除了 $1$ 和它本身外不能被其他正整数整除的数。例如 $2, 5, 13$ 是素数，但 $1$ 和 $6$ 不是素数。
• $1,2,\dots,n$ 的一个排列是指由 $n$ 个互不相同的 $1$ 到 $n$ 组成的数组，顺序任意。例如 $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但出现了 $4$）。

输入格式

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

接下来每组测试用例一行，包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

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

输出格式

对于每组测试用例，输出 $n$ 个整数，表示一个 $1,2,\dots,n$ 的排列，使其“素性”最大。

如果有多种方案，输出任意一种即可。

说明/提示

在第一个测试用例中，共有 $3$ 个满足 $1 \le l \le r \le 2$ 的区间对，其中 $2$ 个区间的 $\operatorname{MEX}$ 是素数：

• $(l,r) = (1,1)$：$\operatorname{MEX}(2) = 1$，不是素数。
• $(l,r) = (1,2)$：$\operatorname{MEX}(2,1) = 3$，是素数。
• $(l,r) = (2,2)$：$\operatorname{MEX}(1) = 2$，是素数。

因此，“素性”为 $2$。在第二个测试用例中，$\operatorname{MEX}(1) = 2$ 是素数，所以“素性”为 $1$。

在第三个测试用例中，最大可能的“素性”为 $8$。

由 ChatGPT 4.1 翻译

样例

3
2
1
5

2 1
1
5 2 1 4 3