C. Build Permutationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputA \mathbf{0}-indexed array a of size n is called good if for all valid indices i (0 \le i \le n-1), a_i + i is a perfect square^\dagger.Given an integer n. Find a permutation^\ddagger p of [0,1,2,\ldots,n-1] that is good or determine that no such permutation exists.^\dagger An integer x is said to be a perfect square if there exists an integer y such that x = y^2.^\ddagger An array b is a permutation of an array a if b consists of the elements of a in arbitrary order. For example, [4,2,3,4] is a permutation of [3,2,4,4] while [1,2,2] is not a permutation of [1,2,3].InputThe first line contains a single integer t (1 \le t \le 10^4) — the number of test cases.The only line of each test case contains a single integer n (1 \le n \le 10^5) — the length of the permutation p.It is guaranteed that the sum of n over all test cases does not exceed 10^5.OutputFor each test case, output n distinct integers p_0, p_1, \dots, p_{n-1} (0 \le p_i \le n-1) — the permutation p — if the answer exists, and -1 otherwise.ExampleInput
3347Output
1 0 2 
0 3 2 1 
1 0 2 6 5 4 3 
NoteIn the first test case, we have n=3. The array p = [1, 0, 2] is good since 1 + 0 = 1^2, 0 + 1 = 1^2, and 2 + 2 = 2^2In the second test case, we have n=4. The array p = [0, 3, 2, 1] is good since 0 + 0 = 0^2, 3 + 1 = 2^2, 2+2 = 2^2, and 1+3 = 2^2.
3347
1 0 2  0 3 2 1  1 0 2 6 5 4 3  
['constructive algorithms', 'dp', 'math', '*1200']