Codeforces Round 987 (Div. 2) |
---|
Finished |
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:
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
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤2⋅105). The description of the test cases follows.
The only line of each test case contains a single integer n (1≤n≤2⋅105) — the number of BBQ buns.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
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.
2312
-1 1 2 3 6 10 2 7 6 10 1 7 3
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.
Name |
---|