Pour un entier strictement positif $n$, une suite de longueur $n$ est appelée « suite de briques rouges » si elle vérifie les conditions suivantes :

• Chacun des entiers $1, 2, \ldots, n$ apparaît exactement une fois dans la suite.
• La somme de chaque paire d'éléments adjacents n'est pas un carré parfait.

Étant donné un entier $n$, construisez une suite de briques rouges de longueur $n$.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^4$), le nombre de cas de test.

Pour chaque cas de test, la seule ligne contient un entier $n$ ($1 \le n \le 4 \times 10^6$), la longueur requise de la suite de briques rouges.

Il est garanti que la somme des $n$ ne dépasse pas $4 \times 10^6$. On peut prouver qu'une solution existe toujours sous les contraintes données.

Sortie

Affichez $T$ lignes, chacune contenant la suite à construire. S'il existe plusieurs réponses, affichez n'importe laquelle d'entre elles.

Exemples

Entrée 1

5
1
2
3
4
5

Sortie 1

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

Remarque

Pour $n = 5$, si la suite affichée est 1 2 3 4 5, la réponse est fausse car $4 + 5 = 9$ est un carré parfait.