La chica mágica Nene tiene una matriz $a$ de $n\times n$ llena de ceros. El $j$-ésimo elemento de la $i$-ésima fila de la matriz $a$ se denota como $a_{i, j}$.

Ella puede realizar operaciones de los siguientes dos tipos con esta matriz:

• Operación de tipo $1$: elegir un entero $i$ entre $1$ y $n$ y una permutación $p_1, p_2, \ldots, p_n$ de enteros del $1$ al $n$. Asignar $a_{i, j}:=p_j$ para todo $1 \le j \le n$ simultáneamente.
• Operación de tipo $2$: elegir un entero $i$ entre $1$ y $n$ y una permutación $p_1, p_2, \ldots, p_n$ de enteros del $1$ al $n$. Asignar $a_{j, i}:=p_j$ para todo $1 \le j \le n$ simultáneamente.

Nene quiere maximizar la suma de todos los números en la matriz $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$. Ella te pide que encuentres la forma de realizar las operaciones para que esta suma sea máxima. Como no quiere realizar demasiadas operaciones, debes proporcionar una solución con no más de $2n$ operaciones.

Una permutación de longitud $n$ es un arreglo que consiste en $n$ enteros distintos del $1$ al $n$ en orden arbitrario. Por ejemplo, $[2,3,1,5,4]$ es una permutación, pero $[1,2,2]$ no es una permutación ($2$ aparece dos veces en el arreglo), y $[1,3,4]$ tampoco es una permutación ($n=3$ pero hay un $4$ en el arreglo).

Entrada

Cada caso de prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \le t \le 500$). A continuación sigue la descripción de los casos de prueba.

La única línea de cada caso de prueba contiene un solo entero $n$ ($1 \le n \le 500$) --- el tamaño de la matriz $a$.

Se garantiza que la suma de $n^2$ sobre todos los casos de prueba no excede $5 \cdot 10^5$.

Salida

Para cada caso de prueba, en la primera línea imprime dos enteros $s$ y $m$ ($0\leq m\leq 2n$) --- la suma máxima de los números en la matriz y el número de operaciones en tu solución.

En la $k$-ésima de las siguientes $m$ líneas, imprime la descripción de la $k$-ésima operación:

• un entero $c$ ($c \in \{1, 2\}$) --- el tipo de la $k$-ésima operación;
• un entero $i$ ($1 \le i \le n$) --- la fila o la columna a la que se aplica la $k$-ésima operación;
• una permutación $p_1, p_2, \ldots, p_n$ de enteros del $1$ al $n$ --- la permutación utilizada en la $k$-ésima operación.

Ten en cuenta que no necesitas minimizar el número de operaciones utilizadas, solo debes usar no más de $2n$ operaciones. Se puede demostrar que la suma máxima posible siempre se puede obtener en no más de $2n$ operaciones.

Ejemplos

Entrada 1

2
1
2

Salida 1

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

Nota

En el primer caso de prueba, la suma máxima $s=1$ se puede obtener en $1$ operación estableciendo $a_{1, 1}:=1$.

En el segundo caso de prueba, la suma máxima $s=7$ se puede obtener en $3$ operaciones de la siguiente manera:

Se puede demostrar que es imposible hacer que la suma de los números en la matriz sea mayor que $7$.