Presidential Election

Two weeks have passed since the presidential election and the result still has not been announced. Instead of waiting, Seongje decided to work out the winner himself.

By some means of his own, Seongje surveyed every single person who voted and recorded how each of them ranks the candidates. A voter always votes according to that ranking.

For example, suppose there are 5 candidates and one voter's ranking is [3, 2, 5, 1, 4]. If candidate 2 and candidate 4 face each other, this voter votes for candidate 2, because 2 comes before 4 in the ranking.

The voting rules are as follows.

• There are $C$ candidates and $V$ voters. Candidates are numbered from 1 to $C$, and $V$ is always odd.
• Voting runs for at most two rounds. In the first round every candidate can receive votes, and a candidate who takes more than half of all votes is elected, which ends the voting.
• If nobody passes half in the first round, only the two candidates with the most votes go to the second round and the vote is held again. The candidate who takes more than half of the votes in the second round is the final winner.
• In the first round, the vote counts of the second place candidate and the third place candidate are always different.
• Each voter's ranking is the same in the first round and in the second round.
• Nobody abstains.

From the rankings Seongje collected, find the final winner and the round in which that candidate was elected.

The first line contains the number of test cases $T$. ($1 \le T \le 100$)

The first line of each test case contains the number of candidates $C$ and the number of voters $V$. ($1 \le C, V \le 100$, and $V$ is odd)

Each of the next $V$ lines contains $C$ integers, the ranking of one voter. The candidate written first is the most preferred one and the candidate written last is the least preferred one.

The $C$ integers on one line contain every integer from 1 to $C$ exactly once.

For each test case, print the number of the elected candidate and the round in which the voting ended (1 or 2) on one line, separated by a space.