Dla dodatniej liczby całkowitej $n$, ciąg o długości $n$ nazywamy „ciągiem z czerwonej cegły”, jeśli spełnia następujące warunki:

• Każda z liczb $1, 2, \ldots, n$ występuje w ciągu dokładnie jeden raz.
• Suma każdej pary sąsiednich elementów nie jest kwadratem liczby całkowitej.

Mając daną liczbę całkowitą $n$, skonstruuj ciąg z czerwonej cegły o długości $n$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego jedyny wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 4 \times 10^6$), oznaczającą wymaganą długość ciągu z czerwonej cegły.

Gwarantuje się, że suma wartości $n$ nie przekracza $4 \times 10^6$. Można udowodnić, że przy podanych ograniczeniach rozwiązanie zawsze istnieje.

Wyjście

Wypisz $T$ wierszy, z których każdy zawiera skonstruowany ciąg. Jeśli istnieje wiele poprawnych odpowiedzi, wypisz dowolną z nich.

Przykład

Wejście 1

5
1
2
3
4
5

Wyjście 1

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

Uwagi

Dla $n = 5$, jeśli wypisany ciąg to 1 2 3 4 5, jest to błędna odpowiedź, ponieważ $4 + 5 = 9$ jest kwadratem liczby całkowitej.