CF2031C Penchick and BBQ Buns

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 $

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

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.

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