A15361. Build Permutation

A $\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]$ .

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

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

In 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^2$

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