C. Нина и магическая матрица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Нины есть матрица $$$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$$$) — максимальную сумму чисел в матрице и количество операций в вашем решении.

В $$$k$$$-й из следующих $$$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$$$ операций.

Пример
Входные данные
2
1
2
Выходные данные
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$$$.