Für eine positive ganze Zahl $n$ wird eine Folge der Länge $n$ eine „Rotziegel-Folge“ genannt, wenn sie die folgenden Bedingungen erfüllt:

• Jede der Zahlen $1, 2, \ldots, n$ kommt genau einmal in der Folge vor.
• Die Summe jedes Paares benachbarter Elemente ist keine Quadratzahl.

Gegeben sei eine ganze Zahl $n$. Konstruiere eine Rotziegel-Folge der Länge $n$.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die Anzahl der Testfälle.

Für jeden Testfall enthält die einzige Zeile eine ganze Zahl $n$ ($1 \le n \le 4 \times 10^6$), die geforderte Länge der Rotziegel-Folge.

Es wird garantiert, dass die Summe von $n$ den Wert $4 \times 10^6$ nicht überschreitet. Es lässt sich beweisen, dass unter den gegebenen Bedingungen immer eine Lösung existiert.

Ausgabe

Gib $T$ Zeilen aus, von denen jede die zu konstruierende Folge enthält. Falls es mehrere Lösungen gibt, gib eine beliebige davon aus.

Beispiele

Eingabe 1

5
1
2
3
4
5

Ausgabe 1

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

Hinweis

Wenn für $n = 5$ die ausgegebene Folge 1 2 3 4 5 lautet, ist dies eine falsche Antwort, da $4 + 5 = 9$ eine Quadratzahl ist.