Per un intero positivo $n$, una sequenza di lunghezza $n$ è chiamata «sequenza di mattoni rossi» se soddisfa le seguenti condizioni:

• Ciascuno dei numeri $1, 2, \ldots, n$ compare esattamente una volta nella sequenza.
• La somma di ogni coppia di elementi adiacenti non è un quadrato perfetto.

Dato un intero $n$, costruisci una sequenza di mattoni rossi di lunghezza $n$.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^4$), il numero di casi di test.

Per ciascun caso di test, l'unica riga contiene un intero $n$ ($1 \le n \le 4 \times 10^6$), la lunghezza richiesta per la sequenza di mattoni rossi.

È garantito che la somma di $n$ non supera $4 \times 10^6$. Si può dimostrare che esiste sempre una soluzione sotto i vincoli dati.

Output

Stampa $T$ righe, ciascuna contenente la sequenza da costruire. Se esistono più risposte valide, stampane una qualsiasi.

Esempi

Input 1

5
1
2
3
4
5

Output 1

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

Note

Per $n = 5$, se la sequenza prodotta in output è 1 2 3 4 5, la risposta è errata perché $4 + 5 = 9$ è un quadrato perfetto.