Problem Description

Affected by the incident, Cirno found that cards sealing her abilities were circulating in Gensokyo.

After investigating, Cirno found that there are a total of $n$ different types of cards, and the total number of each type is exactly $n$. There are $n$ people who bought these cards. Each person bought exactly $n$ cards, and they may buy cards of the same type.

However, Cirno wants everyone to hold exactly $n$ types of cards, so she gathers these $n$ people together and tries to achieve her goal through card exchanges.

Each time, Cirno chooses one card from each of two people and swaps them, until everyone holds exactly $n$ types of cards.

Since each swap reduces the magic on the cards, Cirno wants each card to be swapped at most once.

But she does not know how to swap them, so she asks for your help.

You need to tell her the swapping process, or tell her that no such solution exists.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains a positive integer $n$, as described in the statement.

The next $n$ lines each contain $n$ positive integers. The $j$-th integer in the $i$-th line represents the type of the $j$-th card held by the $i$-th person.

Output Format

For each test case, if there is no solution that makes everyone hold $n$ types of cards, output one line containing $-1$.

Otherwise, first output one line containing a positive integer $m$, the number of swaps.

Then output $m$ lines. Each line contains four positive integers $a,b,c,d$, meaning that the $b$-th card of person $a$ is swapped with the $d$-th card of person $c$.

Note that you must ensure that no card is swapped twice, and after all swaps, each person holds exactly $n$ types of cards.

2
3
1 2 2
2 3 3
3 1 1
3
1 2 3
2 3 1
3 2 1

2
1 3 3 1
2 3 3 2
0

Hint

Sample Explanation.

In the first test case, in the first swap we swap the third card of the first person with the first card of the third person.

In the second swap we swap the third card of the second person with the second card of the third person.

With a total of two swaps, everyone can end up holding three types of cards.

Other valid solutions are also accepted.

In the second test case, since everyone already holds three types of cards at the beginning, no swaps are needed, so output a single line $0$.

Constraints.

Subtask $1$ ($20$ points): Each person holds only one type of card.

Subtask $2$ ($20$ points): Each person holds at least $n-1$ cards of the same type.

Subtask $3$ ($60$ points): No special constraints.

For all testdata, $\sum\limits_{i=1}^{T}n_{i} \leq 200$.

Translated by ChatGPT 5