La magical girl Nene possède une matrice $n \times n$ nommée $a$ remplie de zéros. Le $j$-ième élément de la $i$-ième ligne de la matrice $a$ est noté $a_{i, j}$.

Elle peut effectuer des opérations des deux types suivants sur cette matrice :

• Opération de type $1$ : choisir un entier $i$ entre $1$ et $n$ et une permutation $p_1, p_2, \ldots, p_n$ des entiers de $1$ à $n$. Assigner $a_{i, j}:=p_j$ pour tout $1 \le j \le n$ simultanément.
• Opération de type $2$ : choisir un entier $i$ entre $1$ et $n$ et une permutation $p_1, p_2, \ldots, p_n$ des entiers de $1$ à $n$. Assigner $a_{j, i}:=p_j$ pour tout $1 \le j \le n$ simultanément.

Nene souhaite maximiser la somme de tous les nombres dans la matrice $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$. Elle vous demande de trouver une manière d'effectuer les opérations afin que cette somme soit maximisée. Comme elle ne veut pas effectuer trop d'opérations, vous devez fournir une solution utilisant au plus $2n$ opérations.

Une permutation de longueur $n$ est un tableau composé de $n$ entiers distincts de $1$ à $n$ dans un ordre arbitraire. Par exemple, $[2,3,1,5,4]$ est une permutation, mais $[1,2,2]$ n'est pas une permutation ($2$ apparaît deux fois dans le tableau), et $[1,3,4]$ n'est pas non plus une permutation ($n=3$ mais il y a un $4$ dans le tableau).

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $t$ ($1 \le t \le 500$). La description des cas de test suit.

La seule ligne de chaque cas de test contient un entier unique $n$ ($1 \le n \le 500$) --- la taille de la matrice $a$.

Il est garanti que la somme des $n^2$ sur tous les cas de test ne dépasse pas $5 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez sur la première ligne deux entiers $s$ et $m$ ($0\leq m\leq 2n$) --- la somme maximale des nombres dans la matrice et le nombre d'opérations dans votre solution.

Sur la $k$-ième des $m$ lignes suivantes, affichez la description de la $k$-ième opération :

• un entier $c$ ($c \in \{1, 2\}$) --- le type de la $k$-ième opération ;
• un entier $i$ ($1 \le i \le n$) --- la ligne ou la colonne sur laquelle la $k$-ième opération est appliquée ;
• une permutation $p_1, p_2, \ldots, p_n$ des entiers de $1$ à $n$ --- la permutation utilisée dans la $k$-ième opération.

Notez que vous n'avez pas besoin de minimiser le nombre d'opérations utilisées, vous devez seulement utiliser au plus $2n$ opérations. Il peut être démontré que la somme maximale possible peut toujours être obtenue en au plus $2n$ opérations.

Exemples

Entrée 1

2
1
2

Sortie 1

1 1
1 1 1
7 3
1 1 1 2
1 2 1 2
2 1 1 2

Remarque

Dans le premier cas de test, la somme maximale $s=1$ peut être obtenue en $1$ opération en posant $a_{1, 1}:=1$.

Dans le second cas de test, la somme maximale $s=7$ peut être obtenue en $3$ opérations comme suit :

Il peut être démontré qu'il est impossible de rendre la somme des nombres dans la matrice supérieure à $7$.