311251: CF1956C. Nene's Magical Matrix

C. Nene's Magical Matrixtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The magical girl Nene has an $n\times n$ matrix $a$ filled with zeroes. The $j$-th element of the $i$-th row of matrix $a$ is denoted as $a_{i, j}$.

She can perform operations of the following two types with this matrix:

• Type $1$ operation: choose an integer $i$ between $1$ and $n$ and a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$. Assign $a_{i, j}:=p_j$ for all $1 \le j \le n$ simultaneously.
• Type $2$ operation: choose an integer $i$ between $1$ and $n$ and a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$. Assign $a_{j, i}:=p_j$ for all $1 \le j \le n$ simultaneously.

Nene wants to maximize the sum of all the numbers in the matrix $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$. She asks you to find the way to perform the operations so that this sum is maximized. As she doesn't want to make too many operations, you should provide a solution with no more than $2n$ operations.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of test cases follows.

The only line of each test case contains a single integer $n$ ($1 \le n \le 500$) — the size of the matrix $a$.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, in the first line output two integers $s$ and $m$ ($0\leq m\leq 2n$) — the maximum sum of the numbers in the matrix and the number of operations in your solution.

In the $k$-th of the next $m$ lines output the description of the $k$-th operation:

• an integer $c$ ($c \in \{1, 2\}$) — the type of the $k$-th operation;
• an integer $i$ ($1 \le i \le n$) — the row or the column the $k$-th operation is applied to;
• a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ — the permutation used in the $k$-th operation.

Note that you don't need to minimize the number of operations used, you only should use no more than $2n$ operations. It can be shown that the maximum possible sum can always be obtained in no more than $2n$ operations.

ExampleInput

2
1
2

Output

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

Note

In the first test case, the maximum sum $s=1$ can be obtained in $1$ operation by setting $a_{1, 1}:=1$.

In the second test case, the maximum sum $s=7$ can be obtained in $3$ operations as follows:

It can be shown that it is impossible to make the sum of the numbers in the matrix larger than $7$.

题目大意：
Nene有一个n×n的零矩阵a。她可以通过两种操作来修改矩阵：
1. 选择一行和一个1到n的整数排列，将该行所有元素设置为排列中的对应值。
2. 选择一列和一个1到n的整数排列，将该列所有元素设置为排列中的对应值。
目标是使得矩阵中所有数的和最大。需要找到一种操作方式，使得这个和最大，同时操作次数不超过2n。

输入数据格式：
第一行包含一个整数t，表示测试用例的数量。
接下来t行，每行包含一个整数n，表示矩阵的大小。

输出数据格式：
对于每个测试用例，第一行输出两个整数s和m，分别表示矩阵中所有数的最大和以及操作次数。
接下来m行，每行包含三个部分：
1. 一个整数c（1或2），表示操作的类型。
2. 一个整数i（1到n），表示操作的行或列。
3. 一个1到n的整数排列，表示操作中使用的排列。

请注意，不需要最小化使用的操作次数，只要不超过2n次即可。可以证明，最大可能的和总是可以在不超过2n次操作内获得。题目大意： Nene有一个n×n的零矩阵a。她可以通过两种操作来修改矩阵： 1. 选择一行和一个1到n的整数排列，将该行所有元素设置为排列中的对应值。 2. 选择一列和一个1到n的整数排列，将该列所有元素设置为排列中的对应值。 目标是使得矩阵中所有数的和最大。需要找到一种操作方式，使得这个和最大，同时操作次数不超过2n。 输入数据格式： 第一行包含一个整数t，表示测试用例的数量。 接下来t行，每行包含一个整数n，表示矩阵的大小。 输出数据格式： 对于每个测试用例，第一行输出两个整数s和m，分别表示矩阵中所有数的最大和以及操作次数。 接下来m行，每行包含三个部分： 1. 一个整数c（1或2），表示操作的类型。 2. 一个整数i（1到n），表示操作的行或列。 3. 一个1到n的整数排列，表示操作中使用的排列。 请注意，不需要最小化使用的操作次数，只要不超过2n次即可。可以证明，最大可能的和总是可以在不超过2n次操作内获得。