У волшебницы Нэнэ есть матрица $a$ размера $n \times n$, заполненная нулями. Элемент $j$-го столбца $i$-й строки матрицы $a$ обозначается как $a_{i, j}$.

Она может выполнять с этой матрицей операции двух типов:

• Операция типа $1$: выбрать целое число $i$ от $1$ до $n$ и перестановку $p_1, p_2, \ldots, p_n$ чисел от $1$ до $n$. Присвоить $a_{i, j}:=p_j$ для всех $1 \le j \le n$ одновременно.
• Операция типа $2$: выбрать целое число $i$ от $1$ до $n$ и перестановку $p_1, p_2, \ldots, p_n$ чисел от $1$ до $n$. Присвоить $a_{j, i}:=p_j$ для всех $1 \le j \le n$ одновременно.

Нэнэ хочет максимизировать сумму всех чисел в матрице $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$. Она просит вас найти способ выполнения операций так, чтобы эта сумма была максимальной. Поскольку она не хочет выполнять слишком много операций, вы должны предоставить решение, содержащее не более $2n$ операций.

Перестановка длины $n$ — это массив, состоящий из $n$ различных целых чисел от $1$ до $n$ в произвольном порядке. Например, $[2,3,1,5,4]$ является перестановкой, а $[1,2,2]$ — нет (число $2$ встречается дважды), и $[1,3,4]$ также не является перестановкой (размер $n=3$, но присутствует число $4$).

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке задано количество наборов входных данных $t$ ($1 \le t \le 500$). Далее следует описание наборов входных данных.

Единственная строка каждого набора содержит целое число $n$ ($1 \le n \le 500$) — размер матрицы $a$.

Гарантируется, что сумма $n^2$ по всем наборам входных данных не превышает $5 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных в первой строке выведите два целых числа $s$ и $m$ ($0\leq m\leq 2n$) — максимальную сумму чисел в матрице и количество операций в вашем решении.

В каждой из следующих $m$ строк выведите описание $k$-й операции:

• целое число $c$ ($c \in \{1, 2\}$) — тип $k$-й операции;
• целое число $i$ ($1 \le i \le n$) — строка или столбец, к которому применяется $k$-я операция;
• перестановка $p_1, p_2, \ldots, p_n$ чисел от $1$ до $n$ — перестановка, используемая в $k$-й операции.

Заметьте, что вам не нужно минимизировать количество используемых операций, достаточно использовать не более $2n$ операций. Можно показать, что максимально возможная сумма всегда может быть достигнута не более чем за $2n$ операций.

Примеры

Пример 1

2
1
2

Выходные данные 1

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

Примечание

В первом наборе входных данных максимальная сумма $s=1$ может быть получена за $1$ операцию путем присваивания $a_{1, 1}:=1$.

Во втором наборе входных данных максимальная сумма $s=7$ может быть получена за $3$ операции следующим образом:

Можно показать, что невозможно получить сумму чисел в матрице больше $7$.