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 $10^6$ available fillings of BBQ buns, numbered from $1$ to $10^6$. 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 $|i-j|$, must be a perfect square$^{\text{∗}}$.

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.

$^{\text{∗}}$A positive integer $x$ is a perfect square if there exists a positive integer $y$ such that $x = y^2$. For example, $49$ and $1$ are perfect squares because $49 = 7^2$ and $1 = 1^2$ 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$ ($1 \le t \le 2\cdot 10^5$). The description of the test cases follows.

The only line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of BBQ buns.

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

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.

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=3^2$. Similarly, buns $5$ and $9$ both have filling $10$ and are spaced at a distance of $4=2^2$.