## DMOPC '21 Contest 5 P3 - Permutations & Primes

View as PDF

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

Author:
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 buildings lined up in a row, the -th building having a height of . The heights of the buildings form a permutation of the integers .

The game starts with Nene-Robo standing atop the building with height . The two players then take turns moving Nene-Robo, with Nene going first. In one turn, a player can move Nene-Robo from building to building if and 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 test cases.

#### Constraints

The sum of over all test cases does not exceed .

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

#### Sample Input

2
3
2

#### Sample Output

1 2 3
-1

#### Explanation

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

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