魔法少女 Nene 有一個 $n \times n$ 的矩陣 $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$。