Magiczna dziewczyna Nene posiada macierz $a$ o wymiarach $n \times n$ wypełnioną zerami. $j$-ty element $i$-tego wiersza macierzy $a$ oznaczamy jako $a_{i, j}$.

Może ona wykonywać operacje dwóch następujących typów na tej macierzy:

• Operacja typu $1$: wybierz liczbę całkowitą $i$ z zakresu od $1$ do $n$ oraz permutację $p_1, p_2, \ldots, p_n$ liczb od $1$ do $n$. Przypisz $a_{i, j}:=p_j$ dla wszystkich $1 \le j \le n$ jednocześnie.
• Operacja typu $2$: wybierz liczbę całkowitą $i$ z zakresu od $1$ do $n$ oraz permutację $p_1, p_2, \ldots, p_n$ liczb od $1$ do $n$. Przypisz $a_{j, i}:=p_j$ dla wszystkich $1 \le j \le n$ jednocześnie.

Nene chce zmaksymalizować sumę wszystkich liczb w macierzy $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$. Prosi Cię o znalezienie sposobu wykonania operacji tak, aby ta suma była maksymalna. Ponieważ nie chce wykonywać zbyt wielu operacji, powinieneś podać rozwiązanie wykorzystujące nie więcej niż $2n$ operacji.

Permutacja długości $n$ to tablica składająca się z $n$ różnych liczb całkowitych od $1$ do $n$ w dowolnej kolejności. Na przykład $[2,3,1,5,4]$ jest permutacją, ale $[1,2,2]$ nie jest permutacją ($2$ występuje dwukrotnie w tablicy), a $[1,3,4]$ również nie jest permutacją ($n=3$, ale w tablicy znajduje się $4$).

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $t$ ($1 \le t \le 500$). Następnie podane są opisy przypadków testowych.

Jedyna linia każdego przypadku testowego zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 500$) --- rozmiar macierzy $a$.

Gwarantuje się, że suma $n^2$ dla wszystkich przypadków testowych nie przekracza $5 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego w pierwszej linii wypisz dwie liczby całkowite $s$ oraz $m$ ($0\leq m\leq 2n$) --- maksymalną sumę liczb w macierzy oraz liczbę operacji w Twoim rozwiązaniu.

W $k$-tej z kolejnych $m$ linii wypisz opis $k$-tej operacji:

• liczbę całkowitą $c$ ($c \in \{1, 2\}$) --- typ $k$-tej operacji;
• liczbę całkowitą $i$ ($1 \le i \le n$) --- wiersz lub kolumnę, na której wykonywana jest $k$-ta operacja;
• permutację $p_1, p_2, \ldots, p_n$ liczb od $1$ do $n$ --- permutację używaną w $k$-tej operacji.

Zauważ, że nie musisz minimalizować liczby użytych operacji, powinieneś jedynie użyć nie więcej niż $2n$ operacji. Można wykazać, że maksymalną możliwą sumę zawsze można uzyskać w nie więcej niż $2n$ operacjach.

Przykład

Wejście 1

2
1
2

Wyjście 1

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

Uwagi

W pierwszym przypadku testowym maksymalną sumę $s=1$ można uzyskać w $1$ operacji, ustawiając $a_{1, 1}:=1$.

W drugim przypadku testowym maksymalną sumę $s=7$ można uzyskać w $3$ operacjach w następujący sposób:

Można wykazać, że nie jest możliwe uzyskanie sumy liczb w macierzy większej niż $7$.