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

Пенчик любит две вещи: полные квадраты и булочки барбекю в гонконгском стиле! На его день рождения Коханэ хочет объединить их в один подарок: $$$n$$$ булочек барбекю, расположенных слева направо. Существует $$$10^6$$$ доступных начинок для булочек барбекю, пронумерованных от $$$1$$$ до $$$10^6$$$. Чтобы убедиться, что Пенчику понравится этот подарок, Кохане хочет, чтобы выполнялись следующие условия:

  • Ни одна начинка не используется ровно один раз; то есть каждая начинка должна либо не появляться вовсе, либо появляться как минимум дважды.
  • Для любых двух булочек $$$i$$$ и $$$j$$$ с одинаковой начинкой расстояние между ними, равное $$$|i-j|$$$, должно быть полным квадратом$$$^{\text{∗}}$$$.

Помогите Кохане найти подходящий способ выбора начинки для булочек или определите, что выполнить все условия невозможно. Если существует несколько решений, выведите любое из них.

$$$^{\text{∗}}$$$Целое положительное число $$$x$$$ является полным квадратом, если существует целое положительное число $$$y$$$ такое, что $$$x = y^2$$$. Например, $$$49$$$ и $$$1$$$ — полные квадраты, потому что $$$49 = 7^2$$$ и $$$1 = 1^2$$$ соответственно. С другой стороны, $$$5$$$ не является полным квадратом, так как ни одно целое число в квадрате не равно $$$5$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — количество булочек барбекю.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных, если не существует правильного выбора начинок, выведите $$$-1$$$. В противном случае выведите $$$n$$$ целых чисел, где $$$i$$$-е целое число представляет начинку $$$i$$$-й булочки барбекю. Если существует несколько решений, выведите любое из них.

Пример
Входные данные
2
3
12
Выходные данные
-1
1 2 3 6 10 2 7 6 10 1 7 3
Примечание

В первом наборе входных данных выбор начинок «1 1 1» недопустим, так как булочки $$$1$$$ и $$$3$$$ имеют одинаковую начинку, но находятся на расстоянии $$$2$$$ друг от друга, что не является полным квадратом. Выбор начинок «1 1 2» также недопустим, так как начинка $$$2$$$ используется только один раз.

Во втором наборе входных данных решение корректно, так как ни одна начинка не используется ровно один раз, и любые две булочки с одной и той же начинкой находятся на расстоянии, равном полному квадрату. Например, булочки $$$1$$$ и $$$10$$$ имеют начинку $$$1$$$ и находятся на расстоянии $$$9=3^2$$$. Аналогично, булочки $$$5$$$ и $$$9$$$ имеют начинку $$$10$$$ и находятся на расстоянии $$$4=2^2$$$.