← 返回题目列表

Codeforces · 1844/B

B. 排列和素数

中文机器翻译题面 查看原题

给你一个正整数$$$n$$$。

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

数组 $$$a_1,\dots,a_n$$$ 的素数定义为 $$$(l,r)$$$ 的对数,使得 $$$1 \le l \le r \le n$$$ 和 $$$\operatorname{MEX}(a_l,\dots,a_r)$$$ 是素数。

在 $$$1,2,\dots,n$$$ 的所有排列中找到具有最大可能素数的 $$$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$$$ 的排列,实现最大可能的素数。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
2
1
5

输出 #1

2 1
1
5 2 1 4 3

注意

在第一个测试用例中,有 $$$3$$$ 对 $$$(l,r)$$$ 与 $$$1 \le l \le r \le 2$$$,其中 $$$2$$$ 有素数 $$$\operatorname{MEX}(a_l,\dots,a_r)$$$:

- $$$(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$$$,这是素数。

在第二个测试用例中,$$$\operatorname{MEX}(1) = 2$$$ 是素数,因此素数是 $$$1$$$。

在第三个测试用例中,最大可能的素数是 $$$8$$$。