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

В последовательности целых чисел $$$a$$$ длины $$$n$$$ каждый элемент изначально равен $$$-1$$$.

У Мизуки есть две пишущие машинки, первая из которых пишет слева направо с указателем, изначально указывающим на $$$1$$$, а вторая пишет буквы справа налево с указателем, изначально указывающим на $$$n$$$.

Мизуки выбирает одну из пишущих машинок и выполняет с ней следующие операции, пока $$$a$$$ не превратится в перестановку элементов $$$[1, 2, \ldots, n]$$$:

  • Запись числа: записать минимальное целое положительное число, не встречающееся в $$$a$$$, на позицию $$$a_i$$$. Здесь $$$i$$$ — позиция, на которую указывает указатель. Такая операция может быть выполнена только при $$$a_i = -1$$$.
  • Возврат каретки: возврат указателя на начальную позицию (т.е. $$$1$$$ для первой машинки, $$$n$$$ для второй).
  • Перемещение указателя: переместить указатель на следующую позицию. Пусть $$$i$$$ — это позиция, на которую указывает указатель до этой операции. Если Мизуки использует первую пишущую машинку, то $$$i := i + 1$$$, а в противном случае $$$i := i - 1$$$. Такая операция может быть выполнена только в том случае, если после ее выполнения выполняется условие $$$1 \le i \le n$$$.

Ваша задача — построить любую перестановку $$$p$$$ длины $$$n$$$, такую, чтобы минимальное количество операций возврата каретки, необходимое для того, чтобы получить $$$a = p$$$, было одинаковым независимо от того, какой машинкой пользуется Мизуки.

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

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

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

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

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

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

Если существует несколько допустимых перестановок, вы можете вывести любую из них.

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

В первом наборе входных данных можно сделать $$$a = p = [1]$$$, используя $$$0$$$ операций возврата каретки.

Для второго набора входных данных найдем необходимое количество возвратов каретки, чтобы получить $$$a = p = [1, 2]$$$.

Если Мизуки использует первую пишущую машинку:

  • Запись числа: записать $$$1$$$ в $$$a_1$$$, $$$a$$$ станет $$$[1, -1]$$$.
  • Перемещение указателя: переместить указатель на следующую позицию. (т.е. $$$2$$$).
  • Запись числа: записать $$$2$$$ в $$$a_2$$$, $$$a$$$ станет $$$[1, 2]$$$.

Если Мизуки использует вторую пишущую машинку:

  • Перемещение указателя: переместить указатель на следующую позицию. (т.е. $$$1$$$).
  • Запись числа: записать $$$1$$$ в $$$a_1$$$, $$$a$$$ станет $$$[1, -1]$$$.
  • Возврат каретки: вернуть указатель на $$$2$$$.
  • Запись числа: записать $$$2$$$ в $$$a_2$$$, $$$a$$$ станет $$$[1, 2]$$$.

Можно доказать, что минимальное количество возвратов каретки, необходимое для преобразования $$$a$$$ в $$$p$$$ при использовании первой пишущей машинки, равно $$$0$$$, а при использовании второй — $$$1$$$, поэтому данная перестановка не удовлетворяет условию.

Аналогично, $$$p = [2, 1]$$$ также не является допустимой, поэтому для $$$n = 2$$$ решения не существует.

В третьем примере можно сделать $$$a = p = [3, 1, 2]$$$, требующую $$$1$$$ возврат каретки с использованием первой или второй пишущей машинки. Можно показать, что нельзя записать $$$p$$$ используя $$$0$$$ возвратов каретки.

С помощью первой пишущей машинки можно записать перестановку так:

  • Переместить указатель: переместить указатель на следующую позицию (то есть $$$2$$$)
  • Записать число: записать $$$1$$$ в позицию $$$a_2$$$, $$$a$$$ становится $$$[-1, 1, -1]$$$
  • Переместить указатель: переместить указатель на следующую позицию (то есть $$$3$$$)
  • Записать число: записать $$$2$$$ в позицию $$$a_3$$$, $$$a$$$ становится $$$[-1, 1, 2]$$$
  • Возврат каретки: вернуть указатель в позицию $$$1$$$.
  • Записать число: записать $$$3$$$ в позицию $$$a_1$$$, $$$a$$$ становится $$$[3,1,2]$$$

Используя вторую машинку, можно сделать так:

  • Переместить указатель: переместить указатель на следующую позицию (то есть $$$2$$$)
  • Записать число: записать $$$1$$$ в позицию $$$a_2$$$, $$$a$$$ становится $$$[-1, 1, -1]$$$
  • Возврат каретки: вернуть указатель в позицию $$$3$$$.
  • Записать число: записать $$$2$$$ to $$$a_3$$$, $$$a$$$ становится $$$[-1, 1, 2]$$$
  • Переместить указатель: переместить указатель на следующую позицию (то есть $$$2$$$)
  • Переместить указатель: переместить указатель на следующую позицию (то есть $$$1$$$)
  • Записать число: записать $$$3$$$ to $$$a_1$$$, $$$a$$$ становится $$$[3, 1, 2]$$$