Для положительного целого числа $n$ последовательность длины $n$ называется «краснокирпичной последовательностью», если она удовлетворяет следующим условиям:

• Каждое из чисел $1, 2, \ldots, n$ встречается в последовательности ровно один раз.
• Сумма любой пары соседних элементов не является полным квадратом.

Дано целое число $n$. Постройте краснокирпичную последовательность длины $n$.

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

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

Для каждого набора входных данных единственная строка содержит целое число $n$ ($1 \le n \le 4 \times 10^6$) — требуемую длину краснокирпичной последовательности.

Гарантируется, что сумма $n$ не превосходит $4 \times 10^6$. Можно доказать, что при данных ограничениях решение всегда существует.

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

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

Примеры

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

5
1
2
3
4
5

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

1
1 2
1 2 3
1 2 3 4
1 4 2 3 5

Примечание

При $n = 5$, если вывести последовательность 1 2 3 4 5, это будет неправильным ответом, так как $4 + 5 = 9$ является полным квадратом.