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$$$.

Penchick and BBQ Buns

Examples