如果对于所有有效索引 $$$i$$$ ($$$0 \le i \le n-1$$$),$$$a_i + i$$$ 是一个完美的正方形 $$$^\dagger$$$,则大小为 $$$n$$$ 的 $$$\mathbf{0}$$$ 索引数组 $$$a$$$ 被称为良好。
给定一个整数$$$n$$$。找到 $$$[0,1,2,\ldots,n-1]$$$ 的一个好的排列$$$^\ddagger$$$ $$$p$$$ 或确定不存在这样的排列。
$$$^\dagger$$$ 如果存在一个整数 $$$y$$$ 使得 $$$x = y^2$$$,则整数 $$$x$$$ 被称为完全平方数。
$$$^\ddagger$$$ 数组 $$$b$$$ 是数组 $$$a$$$ 的排列,如果 $$$b$$$ 由 $$$a$$$ 的元素以任意顺序组成。例如,$$$[4,2,3,4]$$$ 是 $$$[3,2,4,4]$$$ 的排列,而 $$$[1,2,2]$$$ 不是 $$$[1,2,3]$$$ 的排列。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 排列 $$$p$$$ 的长度。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 不同的整数 $$$p_0, p_1, \dots, p_{n-1}$$$ ($$$0 \le p_i \le n-1$$$) — 排列 $$$p$$$ — 如果答案存在,否则为 $$$-1$$$。
示例
输入 #1
3 3 4 7
输出 #1
1 0 2 0 3 2 1 1 0 2 6 5 4 3
注意
在第一个测试用例中,我们有 $$$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$$$。