题目描述

给定正整数 $n$，构造一个 $1$ 至 $n$ 的排列 $p_1,p_2,\dots,p_n$ 满足以下条件：

• 对于 $1 \le i \le n$，设 $c_i = \lceil \frac{p_1+p_2+\dots +p_i}{i} \rceil$，则在 $c_1,c_2,\dots,c_n$ 中至少有 $\lfloor \frac{n}{3} \rfloor - 1$ 个质数。

输入格式

本题有多组测试数据。输入的第一行一个整数 $t\ (1 \le t \le 10)$ 表示测试数据组数，接下来依次描述每组测试数据。

每组测试数据输入一行一个整数 $n\ (2 \le n \le 10 ^ 5)$。

输出格式

对于每组数据输出满足题设条件的任意一个排列 $p_1,p_2,\dots,p_n$。保证这样的排列存在。

2
2
3

2 1
2 1 3

对于第一组测试数据，我们有 $c_1 = \lceil \frac{2}{1} \rceil = 2$ 和 $c_2 = \lceil \frac{2+1}{2} \rceil = 2$。两个都是质数。

对于第二组测试数据，$c_1 = c_2 = c_3 = 2$。

题目使用协议

来自 THUPC2025（2025年清华大学学生程序设计竞赛暨高校邀请赛）。

以下『本仓库』皆指 THUPC2025 官方仓库（https://gitlink.org.cn/thusaa/thupc2025final）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。