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.
The first line contains an integer ~T~.
The next ~T~ lines each contain a single integer ~N~, describing one test case.
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.
2 3 2
1 2 3 -1
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.