Niu Niu has recently been learning about sorting and has developed a keen interest in the efficiency of sorting algorithms. To optimize the running time of sorting, Niu Niu has come to you, a participant in the winter camp, for help in designing a computer to perform sorting.

The design of this computer is as follows: The array to be sorted is an array $Q$ of size $n$. The basic unit of computation is a comparator. A comparator can be represented by a triplet $(i, j, t)$, where $i, j, t$ are all positive integers, with $1 \le i < j \le n$. Its function is that at time $t$, if $Q_i > Q_j$, then the values of $Q_i$ and $Q_j$ are swapped; otherwise, nothing happens. * For the computer to operate normally, no two comparators can conflict. Two comparators $(A, B, T_1)$ and $(C, D, T_2)$ conflict if and only if $\{A, B\} \cap \{C, D\} \neq \emptyset$ and $T_1 = T_2$. For example, the comparators $(1, 3, 1)$ and $(2, 4, 1)$ do not conflict, but the comparators $(1, 2, 3)$ and $(2, 3, 3)$ do conflict.

During operation, each comparator in this computer performs its corresponding operation at the specified time according to pre-set parameters. The time required for the computer to run is the maximum value $M$ of the parameters $t$ among all comparators; a smaller value means a shorter running time.

Niu Niu has found that many real-world datasets have their own characteristics. When designing the computer, one often needs to consider these characteristics to achieve good results.

To test the designed computer, Niu Niu has provided 8 test cases with a total of 100 test datasets. Each test case contains $K$ test datasets, i.e., $K$ permutations $P$ of length $n$. Please design a computer for each test dataset with a running time not exceeding $m$, such that for any $i \in [1, K]$, the computer can sort $P_i$.

Input

The input files sort1.in~sort8.in are in the contestant's directory. Each input file starts with an integer $T$ ($1 \le T \le 100$), representing the number of test datasets in this test case, which also represents the score of this test case. In all test cases, $\sum T = 100$.

Each test dataset starts with three integers $K, n, m$ ($1 \le n \le 10^5$, $1 \le K, m \le 10^4$), with meanings as described above. Next, there are $K$ lines, each containing $n$ integers, describing a permutation of $1$ to $n$. The data is guaranteed to be solvable.

Output

For the given 8 input files sort1.in~sort8.in, you need to submit the corresponding output files sort1.out~sort8.out.

For each test dataset, first output an integer $num$ ($1 \le num \le 10^6$) representing the number of comparators in your designed computer. Next, output $num$ lines, each containing 3 integers $u, v, t$ ($1 \le u < v \le n$, $1 \le t \le 150$), describing a comparator $(u, v, t)$ of your computer.

Examples

Input 1

1
3 5 4
1 2 5 3 4
3 4 5 1 2
3 1 4 2 5

Output 1

7
1 2 1
3 4 1
2 3 2
4 5 2
1 2 3
3 4 3
2 3 4

Scoring

Each test case is scored independently, and each test case may yield partial points. The total score for each test case is $T$ points, and the score for each test case is the sum of the scores of all test datasets within it. In each test dataset, if $M \le m$ and $num \le 10^6$, and there are no conflicts between comparators and the computer can correctly sort the $K$ permutations, then the test dataset receives 1 point, otherwise 0 points.

If you output fewer than $T$ computers, we assume your $i$-th computer corresponds to the $i$-th test dataset. If your output does not meet the format requirements, we do not guarantee that you will receive points for that test case.

Testing Your Output

Before testing, switch to the directory of this problem: cd sort

We provide a checker tool to test whether your output file is acceptable. To use this tool, run the following in the terminal: ./checker <input> <output> where <input> is the provided input file and <output> is your output file, for example: ./checker sort1.in sort1.out

After running this program, the checker will provide the test result for each test dataset based on your output, which includes (if your output computer has multiple errors, it will return one of them):

1. Illegal exit: Unknown error.
2. Input file error: The input file is illegal; this will not be triggered if the input file is not modified.
3. The number of the comparators is invalid!: The number of comparators is not in the range $[1, 10^6]$, and the checker will exit immediately.
4. Unexpected EOF: The output file is missing data.
5. The running time of the comparator should be in [1, 150]: The running time $t$ of your comparator is not in the range $[1, 150]$.
6. Invalid sorting network!: The sorting network is illegal, including $u \ge v$, $u < 0$, or conflicts between comparators.
7. Invalid! m=a but M=b: The running time $M$ of the computer exceeds $m$.
8. The answer is incorrect: The sorting network is legal, but it does not correctly sort the input permutations.
9. Correct! m=a and M=b: The sorting network is legal and correctly sorts the input permutations; you will receive 1 point for this test dataset.
10. Total points: a: After the checker runs to the end, it will output an additional line showing your total score. Here $a$ is the score you obtained in this test case.

Subtasks

The partial data characteristics are as follows:

1. For test case 4, for every input permutation $P$, the size of each of its cycles is the same. A cycle can be understood as viewing a permutation $P$ of length $n$ as a directed graph with $n$ nodes and $n$ edges, where there is an edge from $i$ to $P_i$. Each connected component in this graph is a cycle.
2. For test case 7, for every input permutation $P$, there exist several disjoint intervals $[l_i, r_i]$ such that after cyclically shifting each interval $[l_i, r_i]$ once, the array is sorted. An example of a cyclic shift is: $(1, 2, 3, 4)$ cyclically shifted once becomes $(2, 3, 4, 1)$. At the same time, for the first 8 test cases, for every input permutation $P$, there exists an integer $i$ such that after cyclically shifting the interval $[1, i]$ once, the array is sorted.

Note

Please keep the input files sort*.in and your output files sort*.out safe and back them up in time to avoid accidental deletion. Scores obtained by modifying the input files yourself are invalid.