← 返回题目列表

Codeforces · 2037/C

C. Superultra 最喜欢的排列

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

Superultra,一只小熊猫,非常想要原始宝石。在他的梦中,一个声音告诉他,他必须完成以下任务才能获得终身供应的原始宝石。帮助超超!

构造一个长度为 $$$n$$$ 的排列$$$^{\text{*}}$$$ $$$p$$$,使得 $$$p_i + p_{i+1}$$$ 在所有 $$$1 \leq i \leq n - 1$$$ 上是复合 $$$^{\text{†}}$$$。如果不可能,则输出$$$-1$$$。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 排列的长度。

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

输出

对于每个测试用例,如果无法构造$$$p$$$,则在新行上输出$$$-1$$$。否则,在新行上输出 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ 。

示例

输入 #1

2
3
8

输出 #1

-1
1 8 7 3 6 2 4 5

注意

在第一个示例中,可以证明大小为 $$$3$$$ 的所有排列都包含两个相邻元素,其和为素数。例如,在排列 $$$[2,3,1]$$$ 中,和 $$$2+3=5$$$ 是质数。

在第二个示例中,我们可以验证示例输出是否正确,因为 $$$1+8$$$、$$$8+7$$$、$$$7+3$$$、$$$3+6$$$、$$$6+2$$$、$$$2+4$$$ 和 $$$4+5$$$ 都是复合的。可能还有其他正确的结构。