Ingenious Lottery Tickets

Time limit2sMemory limit512 MB

Summary

Count how often each number 1 to 49 appears across n lottery entries, then pick the six most frequent, breaking ties by favoring 7 and then smaller numbers.

Level: Medium4 of 10
Topics: Sorting, Array
Solved: No attempts yet

Problem

Your friend Superstitious Stanley is always getting himself into trouble. This time, in his Super Lotto Pick and Choose plan, he wants to get rich quick by choosing the right numbers to win the lottery. In this lottery, an entry consists of six distinct integers from $1$ to $49$ , written in increasing order. Stanley has compiled a list of the winning entries from the last $n$ days and will use it to pick his numbers.

Stanley chooses the six numbers that appeared most often. When he breaks ties, he prefers smaller numbers, except that he prefers $7$ to every other number. What is Stanley's entry?

Input

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

The first line of each test case contains a single integer $n$ ( $1 \le n \le 1\,000$ ), the number of winning entries Stanley compiled. Each of the next $n$ lines contains one winning entry: six distinct integers from $1$ to $49$ in increasing order, separated by spaces.

Output

For each test case, print one line containing Stanley's six numbers in increasing order, separated by spaces.

Hint

In the first test case, each of the numbers $4$ to $9$ appears twice, and every other number appears at most once.

In the second test case, each of the numbers $1$ to $9$ appears twice. By the tie-breaking rule, Stanley picks $7$ first and then the five smallest numbers.

Examples1

Example 1

Input

2
3
1 2 3 4 5 6
4 5 6 7 8 9
7 8 9 10 11 12
3
1 2 3 4 5 6
4 5 6 7 8 9
1 2 3 7 8 9

Expected output

4 5 6 7 8 9
1 2 3 4 5 7