魔法少女ネネは、$n \times n$ の行列 $a$ を持っており、最初はすべての要素が $0$ で埋められています。行列 $a$ の $i$ 行目の $j$ 番目の要素を $a_{i, j}$ と表記します。

彼女はこの行列に対して、以下の2種類の操作を行うことができます。

• タイプ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$ と代入します。

ネネは行列内のすべての数の和 $\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$ が2回現れているため）。また、$[1,3,4]$ も順列ではありません（$n=3$ ですが $4$ が含まれているため）。

入力

各テストケースには複数のテストケースが含まれます。最初の行にはテストケースの数 $t$ ($1 \le t \le 500$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの唯一の行には、行列 $a$ のサイズを表す整数 $n$ ($1 \le n \le 500$) が含まれます。

すべてのテストケースにおける $n^2$ の総和は $5 \cdot 10^5$ を超えないことが保証されています。

出力

各テストケースについて、最初の行に2つの整数 $s$ と $m$ ($0 \le m \le 2n$) を出力してください。これらはそれぞれ、行列内の数の最大和と、解における操作回数を表します。

続く $m$ 行の各行には、$k$ 番目の操作の説明を出力してください。

• 整数 $c$ ($c \in \{1, 2\}$) --- $k$ 番目の操作のタイプ
• 整数 $i$ ($1 \le i \le n$) --- $k$ 番目の操作を適用する行または列の番号
• 順列 $p_1, p_2, \ldots, p_n$ --- $k$ 番目の操作で使用する $1$ から $n$ までの整数の順列

操作回数を最小化する必要はなく、$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$ は $a_{1, 1} := 1$ と設定する $1$ 回の操作で達成できます。

2番目のテストケースでは、最大和 $s=7$ は以下のように $3$ 回の操作で達成できます。

行列内の数の和を $7$ より大きくすることは不可能であることが示せます。