DMOPC '21 Contest 5 P4 - Permutations & Primes

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Given an integer N, find any permutation p_1, p_2, \dots, p_N of 1, 2, \dots, N that satisfies the following, or report that no such permutation exists:

  1. For all 1 \le i \le N-1, |p_{i+1}-p_i| is prime.
  2. The number of distinct p_{i+1}-p_i as 1 \le i \le N-1 is the minimum possible among all permutations satisfying the first condition.

Note that there is no absolute value in the second condition.

To ensure the integrity of your solution, there may be up to T test cases.


1 \le T,N \le 10^6

The sum of N over all test cases does not exceed 10^6.

Subtask 1 [20%]

N is a multiple of 10.

Subtask 2 [40%]

N is even.

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line contains an integer T.

The next T lines each contain a single integer N, describing one test case.

Output Specification

For each test case, if no such permutation exists, output -1 on a line by itself. Otherwise, output N space-separated integers p_1, p_2, \dots, p_N, a permutation that satisfies the conditions.

Sample Input


Sample Output

3 1 4 2


For the first test case, |1-3| = 2, |4-1| = 3, and |2-4| = 2 are all primes, and there are 2 distinct numbers among 1-3 = -2, 4-1 = 3, and 2-4 = -2.

For the second test case, it is not possible for all adjacent absolute differences to be prime.


There are no comments at the moment.