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

Вам задана массив $$$a$$$ длины $$$n$$$, состоящий из нулей. Вы выполняете $$$n$$$ действий с этим массивом: в течение $$$i$$$-го действия происходит следующая последовательность операций:

  1. Выбирается максимальный по длине подмассив (последовательный подотрезок), состоящий только из нулей, среди всех таких отрезков выбирается самый левый;
  2. Пусть этот отрезок равен $$$[l; r]$$$. Если $$$r-l+1$$$ нечетно (не делится на $$$2$$$), то присваивается $$$a[\frac{l+r}{2}] := i$$$ (где $$$i$$$ — номер текущего действия), иначе (если $$$r-l+1$$$ четно) присваивается $$$a[\frac{l+r-1}{2}] := i$$$.

Рассмотрим массив $$$a$$$ длины $$$5$$$ (изачально $$$a=[0, 0, 0, 0, 0]$$$). Тогда он меняется следующим образом:

  1. Сначала мы выбираем отрезок $$$[1; 5]$$$ и присваиваем $$$a[3] := 1$$$, таким образом $$$a$$$ становится равен $$$[0, 0, 1, 0, 0]$$$;
  2. затем мы выбираем отрезок $$$[1; 2]$$$ и присваиваем $$$a[1] := 2$$$, таким образом $$$a$$$ становится равен $$$[2, 0, 1, 0, 0]$$$;
  3. затем мы выбираем отрезок $$$[4; 5]$$$ и присваиваем $$$a[4] := 3$$$, таким образом $$$a$$$ становится равен $$$[2, 0, 1, 3, 0]$$$;
  4. затем мы выбираем отрезок $$$[2; 2]$$$ и присваиваем $$$a[2] := 4$$$, таким образом $$$a$$$ становится равен $$$[2, 4, 1, 3, 0]$$$;
  5. и наконец мы выбираем отрезок $$$[5; 5]$$$ и присваиваем $$$a[5] := 5$$$, таким образом $$$a$$$ становится равен $$$[2, 4, 1, 3, 5]$$$.

Ваша задача — найти массив $$$a$$$ длины $$$n$$$ после выполнения всех $$$n$$$ действий. Заметьте, что ответ существует и единственен.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

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

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

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

Для каждого набора тестовых данных выведите ответ — массив $$$a$$$ длины $$$n$$$ после выполнения $$$n$$$ действий, описанных в условии задачи. Заметьте, что ответ существует и единственен.

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