魔法少女 Nene 有一个 $n \times n$ 的矩阵 $a$，初始时矩阵中全是 $0$。矩阵 $a$ 第 $i$ 行第 $j$ 列的元素记作 $a_{i, j}$。

她可以对该矩阵执行以下两种类型的操作：

• 类型 $1$ 操作：选择一个 $1$ 到 $n$ 之间的整数 $i$ 和一个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$。同时将 $a_{i, j}$ 赋值为 $p_j$，其中 $1 \le j \le n$。
• 类型 $2$ 操作：选择一个 $1$ 到 $n$ 之间的整数 $i$ 和一个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$。同时将 $a_{j, i}$ 赋值为 $p_j$，其中 $1 \le j \le n$。

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

说明

在第一个测试用例中，通过设置 $a_{1, 1}:=1$，可以在 $1$ 次操作内得到最大和 $s=1$。

在第二个测试用例中，可以通过以下 $3$ 次操作得到最大和 $s=7$：

可以证明，矩阵中数字的和不可能大于 $7$。