Given an integer , find any permutation
of
that satisfies the following, or report that no such permutation exists:
- For all
,
is prime.
- The number of distinct
as
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 test cases.
Constraints
The sum of over all test cases does not exceed
.
Subtask 1 [20%]
is a multiple of
.
Subtask 2 [40%]
is even.
Subtask 3 [40%]
No additional constraints.
Input Specification
The first line contains an integer .
The next lines each contain a single integer
, describing one test case.
Output Specification
For each test case, if no such permutation exists, output on a line by itself. Otherwise, output
space-separated integers
, a permutation that satisfies the conditions.
Sample Input
2
4
3
Sample Output
3 1 4 2
-1
Explanation
For the first test case, ,
, and
are all primes, and there are
distinct numbers among
,
, and
.
For the second test case, it is not possible for all adjacent absolute differences to be prime.
Comments