마법 소녀 네네는 $n \times n$ 크기의 행렬 $a$를 가지고 있으며, 모든 원소는 $0$으로 채워져 있습니다. 행렬 $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$로 설정합니다.

네네는 행렬의 모든 수의 합인 $\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$)가 주어집니다. 각 테스트 케이스에 대한 설명이 이어집니다.

각 테스트 케이스의 유일한 줄에는 행렬 $a$의 크기를 나타내는 정수 $n$ ($1 \le n \le 500$)이 주어집니다.

모든 테스트 케이스에 대한 $n^2$의 합은 $5 \cdot 10^5$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해, 첫 번째 줄에 행렬의 최대 합 $s$와 사용한 연산 횟수 $m$ ($0 \le m \le 2n$)을 출력하십시오.

다음 $m$개의 줄 중 $k$번째 줄에는 $k$번째 연산에 대한 설명을 출력하십시오.

• 정수 $c$ ($c \in \{1, 2\}$) --- $k$번째 연산의 유형;
• 정수 $i$ ($1 \le i \le n$) --- $k$번째 연산이 적용되는 행 또는 열;
• 순열 $p_1, p_2, \ldots, p_n$ ($1$부터 $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$보다 크게 만드는 것은 불가능함이 증명되어 있습니다.