Cô gái phép thuật Nene có một ma trận $a$ kích thước $n \times n$ chứa toàn các số không. Phần tử thứ $j$ của hàng thứ $i$ trong ma trận $a$ được ký hiệu là $a_{i, j}$.

Cô ấy có thể thực hiện các thao tác thuộc hai loại sau với ma trận này:

• Thao tác loại $1$: chọn một số nguyên $i$ từ $1$ đến $n$ và một hoán vị $p_1, p_2, \ldots, p_n$ của các số nguyên từ $1$ đến $n$. Gán $a_{i, j}:=p_j$ cho tất cả $1 \le j \le n$ cùng một lúc.
• Thao tác loại $2$: chọn một số nguyên $i$ từ $1$ đến $n$ và một hoán vị $p_1, p_2, \ldots, p_n$ của các số nguyên từ $1$ đến $n$. Gán $a_{j, i}:=p_j$ cho tất cả $1 \le j \le n$ cùng một lúc.

Nene muốn tối đa hóa tổng của tất cả các số trong ma trận $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$. Cô ấy nhờ bạn tìm cách thực hiện các thao tác để tổng này đạt giá trị lớn nhất. Vì cô ấy không muốn thực hiện quá nhiều thao tác, bạn cần đưa ra một lời giải với không quá $2n$ thao tác.

Một hoán vị độ dài $n$ là một mảng gồm $n$ số nguyên phân biệt từ $1$ đến $n$ theo thứ tự bất kỳ. Ví dụ, $[2,3,1,5,4]$ là một hoán vị, nhưng $[1,2,2]$ không phải là hoán vị ($2$ xuất hiện hai lần trong mảng), và $[1,3,4]$ cũng không phải là hoán vị ($n=3$ nhưng có số $4$ trong mảng).

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa số lượng trường hợp thử nghiệm $t$ ($1 \le t \le 500$). Tiếp theo là mô tả của các trường hợp thử nghiệm.

Dòng duy nhất của mỗi trường hợp thử nghiệm chứa một số nguyên $n$ ($1 \le n \le 500$) --- kích thước của ma trận $a$.

Đảm bảo rằng tổng của $n^2$ trên tất cả các trường hợp thử nghiệm không vượt quá $5 \cdot 10^5$.

Dữ liệu ra

Đối với mỗi trường hợp thử nghiệm, ở dòng đầu tiên, hãy in ra hai số nguyên $s$ và $m$ ($0\leq m\leq 2n$) --- tổng lớn nhất của các số trong ma trận và số lượng thao tác trong lời giải của bạn.

Trong dòng thứ $k$ của $m$ dòng tiếp theo, hãy in ra mô tả của thao tác thứ $k$:

• một số nguyên $c$ ($c \in \{1, 2\}$) --- loại của thao tác thứ $k$;
• một số nguyên $i$ ($1 \le i \le n$) --- hàng hoặc cột mà thao tác thứ $k$ được áp dụng;
• một hoán vị $p_1, p_2, \ldots, p_n$ của các số nguyên từ $1$ đến $n$ --- hoán vị được sử dụng trong thao tác thứ $k$.

Lưu ý rằng bạn không cần phải tối thiểu hóa số lượng thao tác sử dụng, bạn chỉ cần sử dụng không quá $2n$ thao tác. Có thể chứng minh rằng tổng lớn nhất có thể luôn đạt được trong không quá $2n$ thao tác.

Ví dụ

Ví dụ 1

2
1
2

Kết quả 1

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

Ghi chú

Trong trường hợp thử nghiệm đầu tiên, tổng lớn nhất $s=1$ có thể đạt được trong $1$ thao tác bằng cách đặt $a_{1, 1}:=1$.

Trong trường hợp thử nghiệm thứ hai, tổng lớn nhất $s=7$ có thể đạt được trong $3$ thao tác như sau:

Có thể chứng minh rằng không thể làm cho tổng các số trong ma trận lớn hơn $7$.