DMOPC '21 Contest 5 P3 - Permutations & Primes

View as PDF

Submit solution

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

Problem types

Nene and Tsukasa are battling it out in Rui's newly made video game, Nene-Robo Adventures! The game is played in a city of N buildings lined up in a row, the i-th building having a height of p_i. The heights of the buildings p_1, p_2, \dots, p_N form a permutation of the integers 1, 2, \dots, N.

The game starts with Nene-Robo standing atop the building with height N. The two players then take turns moving Nene-Robo, with Nene going first. In one turn, a player can move Nene-Robo from building i to building j if p_i > p_j and |i-j| is a prime number. The first player who cannot make a move loses, and the other player wins.

Before the game starts, Rui thinks it would be funny if the arrangement of the buildings allowed Nene to win even if both players played optimally. He is curious about the lexicographically smallest permutation of heights with this property. As the only bandmate not yet involved in this scheme, please inform Rui of this arrangement or determine that no such arrangement exists.

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


1 \le T, N \le 10^5

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

Subtask 1 [40%]

T = 1

Subtask 2 [60%]

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 there is no permutation of the heights that guarantees Nene's win with optimal play, output -1 on a line by itself. Otherwise, output N space-separated integers p_1, p_2, \dots, p_N, the lexicographically smallest permutation of heights with the aforementioned property.

Sample Input


Sample Output

1 2 3


For the first test case, Nene can choose to move Nene-Robo from building 3 to building 1, winning the game immediately.

For the second test case, both [1, 2] and [2, 1] would be an instant victory for Tsukasa.


There are no comments at the moment.