本题没有可用的提交语言。

题目描述

给定正整数 $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

提示

样例 #1 解释

对于第一组测试数据，我们有 $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 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public。