B. Bog the Frog
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bog the Frog lives in a peaceful pond containing $$$n$$$ lily pads, uniquely numbered from $$$1$$$ to $$$n$$$. He wants to plan a journey to visit every single lily pad exactly once.

Bog can begin his journey from any lily pad. However, Bog has strict jumping rules: he can only leap from his current lily pad to the next one if the absolute difference between their numbers is a prime number.

Because Bog likes to keep his travel logs neatly organized, he wants his path to be the lexicographically smallest$$$^{\text{∗}}$$$ sequence possible. Can you help Bog find the perfect sequence of lily pads to jump to, or tell him if such a journey is impossible?

$$$^{\text{∗}}$$$An array $$$a$$$ is lexicographically smaller than array $$$b$$$ if there exists an index $$$i$$$ such that $$$a_j=b_j$$$ for all indices $$$1≤j \lt i$$$ and $$$a_i \lt b_i$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each test case consists of a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of lily pads in the pond.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print $$$n$$$ space-separated integers — the lexicographically smallest valid jumping sequence. If no valid sequence exists, output $$$-1$$$.

Example
Input
3
1
2
4
Output
1
-1
2 4 1 3
Note

In the third test case, the jump sequence $$$(2,4,1,3)$$$ follows prime differences:

  • $$$|2-4|=2$$$
  • $$$|4-1|=3$$$
  • $$$|1-3|=2$$$
It can be shown that no sequence lexicographically smaller than this is a valid sequence.