Fyrir jákvæða heiltölu $n$ er runa af lengd $n$ kölluð „rauðmúrsteinaruna“ ef hún uppfyllir eftirfarandi skilyrði:

• Hver talnanna $1, 2, \ldots, n$ kemur nákvæmlega einu sinni fyrir í rununni.
• Summa hvers pars aðliggjandi staka er ekki ferningstala.

Gefin er heiltala $n$. Smíðið rauðmúrsteinarunu af lengd $n$.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur eina línan heiltölu $n$ ($1 \le n \le 4 \times 10^6$), umbeðna lengd rauðmúrsteinarununnar.

Tryggt er að summa $n$ fari ekki yfir $4 \times 10^6$. Sanna má að lausn sé alltaf til undir gefnum skorðum.

Úttak

Prentið $T$ línur, þar sem hver lína inniheldur rununa sem á að smíða. Ef fleiri en eitt svar kemur til greina má prenta hvert þeirra sem er.

Dæmi

Inntak 1

5
1
2
3
4
5

Úttak 1

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

Athugasemd

Fyrir $n = 5$, ef úttaksrunan er 1 2 3 4 5, þá er það rangt svar vegna þess að $4 + 5 = 9$ er ferningstala.