CF2071B Perfecto

A permutation $ p $ of length $ n $ $ ^{\text{∗}} $ is perfect if, for each index $ i $ ( $ 1 \le i \le n $ ), it satisfies the following: - The sum of the first $ i $ elements $ p_1 + p_2 + \ldots + p_i $ is not a perfect square $ ^{\text{†}} $ . You would like things to be perfect. Given a positive integer $ n $ , find a perfect permutation of length $ n $ , or print $ -1 $ if none exists. $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array). $ ^{\text{†}} $ A perfect square is an integer that is the square of an integer, e.g., $ 9=3^2 $ is a perfect square, but $ 8 $ and $ 14 $ are not.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first and only line of each test case contains a single integer $ n $ ( $ 1 \le n \le 5 \cdot 10^5 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case: - If no solution exists, print a single integer $ -1 $ . - Otherwise, print $ n $ integers $ p_1,p_2,\ldots,p_n $ — the perfect permutation you find. If there are multiple solutions, print any of them.

In the first test case, there is only one permutation with length $ n = 1 $ that is $ p = [1] $ , which is not perfect: - $ p_1 = 1 = x^2 $ for $ x = 1 $ . In the second test case, one possible perfect permutation with length $ n = 4 $ is $ p = [2, 4, 1, 3] $ : - $ p_1 = 2 \neq x^2 $ ; - $ p_1 + p_2 = 2 + 4 = 6 \neq x^2 $ ; - $ p_1 + p_2 + p_3 = 2 + 4 + 1 = 7 \neq x^2 $ ; - $ p_1 + p_2 + p_3 + p_4 = 2 + 4 + 1 + 3 = 10 \neq x^2 $ . In the third test case, one possible perfect permutation with length $ n = 5 $ is $ p = [5, 1, 4, 3, 2] $ : - $ p_1 = 5 \neq x^2 $ ; - $ p_1 + p_2 = 5 + 1 = 6 \neq x^2 $ ; - $ p_1 + p_2 + p_3 = 5 + 1 + 4 = 10 \neq x^2 $ ; - $ p_1 + p_2 + p_3 + p_4 = 5 + 1 + 4 + 3 = 13 \neq x^2 $ ; - $ p_1 + p_2 + p_3 + p_4 + p_5 = 5 + 1 + 4 + 3 + 2 = 15 \neq x^2 $ .