问题 J: Permutation and Primes
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Given n, you should construct a permutation P of {1, 2, . . . , n} satisfying that for all 1 ≤ i < n, either
Pi + Pi+1 is an odd prime or |Pi − Pi+1| is an odd prime.
If multiple solutions exist, print any of them. If no solution, print “-1” in one line.
输入
The first line contains one integer T (1 ≤ T ≤ 105
), denoting the number of test cases.
For each test case, input only one line containing one integer n (2 ≤ n ≤ 105
).
It is guaranteed that the sum of n among all test cases in one test file does not exceed 106
.
输出
For each test case:
If solution exists, print one line containing n integers P1, P2, . . . , Pn (1 ≤ Pi ≤ n, ∀ 1 ≤ i < j ≤ n, Pi 6= Pj ),
denoting the permutation you construct.
If no solution, print “-1” in one line.
样例输入 复制
2
3
5样例输出 复制
1 2 3
5 2 1 4 3提示
In the first test case, 1 + 2 = 3, 2 + 3 = 5 are odd primes.
In the second test case, |5 − 2| = 3, 2 + 1 = 3, |1 − 4| = 3, 4 + 3 = 7 are odd primes.