31597번 - Duplicates 스페셜 저지다국어

문제

We say that a number sequence contains duplicates if there is an element that appears more than once in the sequence. Formally, a sequence $(a_1, \dots , a_n)$ contains duplicates if there exist two indices $i$ and $j$ such that $i \ne j$ and $a_i = a_j$.

You are given an $n \times n$ matrix $X$. Each entry in $X$ is an integer between 1ドル$ and $n,ドル inclusive. You can modify zero or more entries in $X$ to arbitrary integers between 1ドル$ and $n,ドル inclusive. Different entries can be modified to different integers.

Your task is to make modifications to entries of $X$ such that all of the following hold:

• For each row $i,ドル the sequence $(X_{i1}, X_{i2}, \dots , X_{in})$ contains duplicates.
• For each column $j,ドル the sequence $(X_{1j }, X_{2j}, \dots , X_{nj})$ contains duplicates.

Compute the minimum number of entries that need to be modified to achieve this. Also, find one possible set of modifications to do it. For each modification, you have to specify which entry will be modified and to what value. Note that the minimum number of entries to be modified can be zero when the given matrix $X$ already satisfies the conditions above.

입력

The first line of input contains one integer $t$ (1ドル ≤ t ≤ 1000$) representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.

The first line of a test case contains one integer $n$ (3ドル ≤ n ≤ 100$). Each of the next $n$ lines contains $n$ integers. The $j$-th integer in the $i$-th line denotes $X_{ij}$ (1ドル ≤ X_{ij} ≤ n$).

The sum of $n^2$ across all test cases in one input file does not exceed 10ドル,円 000$.

출력

For each test case, output a set of modifications in the following format.

On the first line, output an integer $m$ representing the minimum number of entries that need to be modified. On each of the next $m$ lines, output three integers $i,ドル $j,ドル and $v$. This represents a single modification where the entry $X_{ij}$ will be modified to $v$. All of the three integers must be between 1ドル$ and $n,ドル inclusive.

If there are multiple solutions, you can output any of them.

제한

힌트