Due to the influence of an anomaly, Cirno has discovered that cards capable of sealing her powers are circulating throughout Gensokyo.

After investigating, Cirno found that there are $n$ different types of cards, with exactly $n$ cards of each type in total. There are $n$ people who have purchased these cards, and each person has purchased exactly $n$ cards, potentially including multiple cards of the same type.

Cirno wants everyone to hold exactly one of each of the $n$ types of cards. To achieve this, she has gathered these $n$ people together and wants to reach her goal through card exchanges.

In each step, Cirno chooses one card from one person and one card from another person and swaps them. She repeats this process until everyone holds exactly $n$ distinct types of cards.

Since each exchange reduces the magic power of the cards, Cirno wants each card to be exchanged at most once.

She is struggling with how to perform these exchanges and has turned to you for help.

You need to provide her with the sequence of exchanges, or inform her if no such plan exists.

Input

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

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

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

Output

For each test case, if there is no way to make everyone hold $n$ distinct types of cards, output a single line containing -1.

Otherwise, first output a single line containing a positive integer $m$, representing the number of exchanges.

Then, output $m$ lines, each containing four positive integers $a, b, c, d$, indicating that the $b$-th card of the $a$-th person is swapped with the $d$-th card of the $c$-th person.

Note that you must ensure that no card is exchanged more than once, and that after all exchanges, everyone holds exactly $n$ distinct types of cards.

Examples

Input 1

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

Output 1

2
1 3 3 1
2 3 3 2
0

Note 1

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

Then, we swap the third card of the second person with the second card of the third person;

A total of two exchanges are made, allowing everyone to hold three types of cards.

Other valid solutions are also permitted.

In the second test case, since everyone already holds three types of cards at the beginning, no exchanges are needed, so we output 0.

Subtasks

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 restrictions.

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