B. Совершенство
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановка $$$p$$$ длины $$$n$$$$$$^{\text{∗}}$$$ называется совершенной, если для каждого индекса $$$i$$$ ($$$1 \le i \le n$$$) выполняется следующее:

  • Сумма первых $$$i$$$ элементов $$$p_1 + p_2 + \ldots + p_i$$$ не является совершенным квадратом$$$^{\text{†}}$$$.

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

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Совершенный квадрат — это целое число, которое является квадратом целого числа. Например, $$$9=3^2$$$ является совершенным квадратом, а $$$8$$$ и $$$14$$$ — нет.

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

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

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

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных:

  • Если решение не существует, выведите одно целое число $$$-1$$$.
  • В противном случае выведите $$$n$$$ целых чисел $$$p_1,p_2,\ldots,p_n$$$ — совершенную перестановку, которую вы нашли.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
3
1
4
5
Выходные данные
-1
2 4 1 3
5 1 4 3 2
Примечание

В первом наборе входных данных существует только одна перестановка длины $$$n = 1$$$, которая равна $$$p = [1]$$$, и она не является совершенной:

  • $$$p_1 = 1 = x^2$$$ для $$$x = 1$$$.

Во втором наборе входных данных одной из возможных совершенных перестановок длины $$$n = 4$$$ является $$$p = [2, 4, 1, 3]$$$:

  • $$$p_1 = 2 \neq x^2$$$;
  • $$$p_1 + p_2 = 2 + 4 = 6 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 = 2 + 4 + 1 = 7 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 + p_4 = 2 + 4 + 1 + 3 = 10 \neq x^2$$$.

В третьем наборе входных данных одной из возможных совершенных перестановок длины $$$n = 5$$$ является $$$p = [5, 1, 4, 3, 2]$$$:

  • $$$p_1 = 5 \neq x^2$$$;
  • $$$p_1 + p_2 = 5 + 1 = 6 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 = 5 + 1 + 4 = 10 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 + p_4 = 5 + 1 + 4 + 3 = 13 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 + p_4 + p_5 = 5 + 1 + 4 + 3 + 2 = 15 \neq x^2$$$.