Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

C. Penchick and BBQ Buns
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Penchick loves two things: square numbers and Hong Kong-style BBQ buns! For his birthday, Kohane wants to combine them with a gift: n BBQ buns arranged from left to right. There are 106 available fillings of BBQ buns, numbered from 1 to 106. To ensure that Penchick would love this gift, Kohane has a few goals:

  • No filling is used exactly once; that is, each filling must either not appear at all or appear at least twice.
  • For any two buns i and j that have the same filling, the distance between them, which is |ij|, must be a perfect square.

Help Kohane find a valid way to choose the filling of the buns, or determine if it is impossible to satisfy her goals! If there are multiple solutions, print any of them.

A positive integer x is a perfect square if there exists a positive integer y such that x=y2. For example, 49 and 1 are perfect squares because 49=72 and 1=12 respectively. On the other hand, 5 is not a perfect square as no integer squared equals 5

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1t2105). The description of the test cases follows.

The only line of each test case contains a single integer n (1n2105) — the number of BBQ buns.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case, if no valid choice of fillings exists, output 1. Otherwise, output n integers, where the i-th integer represents the filling of the i-th BBQ bun. If there are multiple solutions, print any of them.

Example
Input
2
3
12
Output
-1
1 2 3 6 10 2 7 6 10 1 7 3
Note

In the first test case, the choice of fillings "1 1 1" is not allowed because buns 1 and 3 have the same filling, but are distance 2 apart, which is not a perfect square. The choice of fillings "1 1 2" is also not allowed as filling 2 is only used once.

In the second test case, the solution is valid because no filling is used exactly once, and any two buns with the same filling are spaced at a distance equal to a perfect square. For example, buns 1 and 10 both have filling 1 and are spaced at a distance of 9=32. Similarly, buns 5 and 9 both have filling 10 and are spaced at a distance of 4=22.