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

一个大小为 $n$ 的、以 $\mathbf{0}$ 为起始索引的数组 $a$ 被称为好数组，当且仅当对所有合法下标 $i$（即 $0 \le i \le n-1$），$a_i + i$ 均为完全平方数$^\dagger$。

给定一个整数 $n$，请找出 $[0,1,2,\ldots,n-1]$ 的一个排列$^\ddagger$ $p$，使得 $p$ 是好数组；若不存在这样的排列，则判定其不存在。

$^\dagger$ 整数 $x$ 被称为完全平方数，当且仅当存在整数 $y$，使得 $x = y^2$。

$^\ddagger$ 数组 $b$ 是数组 $a$ 的一个排列，当且仅当 $b$ 由 $a$ 的所有元素以任意顺序组成。例如，$[4,2,3,4]$ 是 $[3,2,4,4]$ 的一个排列，而 $[1,2,2]$ 不是 $[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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例仅有一行，包含一个整数 $n$（$1 \le n \le 10^5$）—— 排列 $p$ 的长度。

保证所有测试用例的 $n$ 之和不超过 $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.

对于每个测试用例，如果答案存在，则输出 $n$ 个互不相同的整数 $p_0, p_1, \dots, p_{n-1}$（满足 $0 \le p_i \le n-1$），即排列 $p$；否则输出 $-1$。

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

在第一个测试用例中，我们有 $n=3$。数组 $p = [1, 0, 2]$ 是“好”的，因为 $1 + 0 = 1^2$、$0 + 1 = 1^2$ 且 $2 + 2 = 2^2$。

在第二个测试用例中，我们有 $n=4$。数组 $p = [0, 3, 2, 1]$ 是“好”的，因为 $0 + 0 = 0^2$、$3 + 1 = 2^2$、$2+2 = 2^2$ 且 $1+3 = 2^2$。