魔法少女 Nene 有一个大小为 $n\times n$ 且初始全为 $0$ 的矩阵 $a$。矩阵 $a$ 的第 $i$ 行第 $j$ 列的元素表示为 $a_{i, j}$。

她可以对这个矩阵进行以下两种类型的操作：

• 第 $1$ 类操作：选择一个介于 $1$ 和 $n$ 之间的整数 $i$，以及一个由 $1$ 到 $n$ 的整数组成的排列 $p_1, p_2, \ldots, p_n$。同时将所有 $1 \le j \le n$ 的 $a_{i, j}$ 赋值为 $p_j$。
• 第 $2$ 类操作：选择一个介于 $1$ 和 $n$ 之间的整数 $i$，以及一个由 $1$ 到 $n$ 的整数组成的排列 $p_1, p_2, \ldots, p_n$。同时将所有 $1 \le j \le n$ 的 $a_{j, i}$ 赋值为 $p_j$。

Nene 希望最大化矩阵中所有数字的和 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$。她请你找到一种操作方案，使得该总和最大。由于她不想进行太多次操作，你提供的方案中操作次数不能超过 $2n$。

长度为 $n$ 的排列是指一个由 $1$ 到 $n$ 的 $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$ 行输出第 $k$ 次操作的描述：

• 一个整数 $c$ ($c \in \{1, 2\}$)，表示第 $k$ 次操作的类型；
• 一个整数 $i$ ($1 \le i \le n$)，表示第 $k$ 次操作作用的行或列；
• 一个由 $1$ 到 $n$ 的整数组成的排列 $p_1, p_2, \ldots, p_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$。