C. Постройте перестановку
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$a$$$ длины $$$n$$$, пронумерованный с $$$\mathbf{0}$$$, называется хорошим, если для всех корректных индексов $$$i$$$ ($$$0 \le i \le n-1$$$) значение $$$a_i + i$$$ является полным квадратом$$$^\dagger$$$.

Дано целое число $$$n$$$. Найдите перестановку$$$^\ddagger$$$ $$$p$$$ массива $$$[0,1,2,\ldots,n-1]$$$, являющуюся хорошим массивом, или определите, что такой перестановки не существует.

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

Входные данные

Первая строка содержит одно целое число $$$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$$$ иначе.

Пример
Входные данные
3
3
4
7
Выходные данные
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$$$.