终于到了选出新总统的时候了，你感到非常兴奋。你知道最终结果可能需要几周时间才能公布，而你实在等不及想看到结果了。

你不知怎么弄到了每位选民的偏好列表（我们不在乎你是怎么弄到这些信息的！）。每位选民都按照自己最喜欢的候选人到最不喜欢的候选人对所有候选人进行了排序。在投票时，选民会投票给其偏好列表中排在最前面的候选人。例如，如果有 5 名候选人（编号为 1 到 5），某位选民的偏好列表是 $[3, 2, 5, 1, 4]$，且当前投票过程中正在竞争的候选人是 2 和 4，那么该选民将投票给候选人 2。

以下是选举过程的规则：

1. 有 $C$ 名候选人（编号从 1 到 $C$）和 $V$ 名选民（$V$ 总是奇数）。
2. 选举过程最多包含 2 轮。所有候选人参加第一轮。如果某位候选人获得了超过 50% 的选票，他将获胜；否则将进行第二轮投票，只有在第一轮中得票数最高的前 2 名候选人进入第二轮。在第二轮中，获得更多选票的候选人将获胜并成为新总统。
3. 你可以放心地假设，给定的偏好不会导致第一轮中第二名和第三名候选人获得相同票数的情况。
4. 选民的偏好在两轮中保持不变，且每位选民在每一轮中必须根据其偏好对当前正在竞争的候选人投下且仅投下一次票。

给定偏好列表，你需要编写一个程序来计算出哪位候选人会获胜，以及是在哪一轮获胜的。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。接下来是各个测试用例，每个测试用例的第一行包含两个整数 $C$ 和 $V$，用空格隔开。$C$ 和 $V$（$1 \le C, V \le 100$）分别代表候选人和选民的数量，随后是 $V$ 行，每行包含 $C$ 个用空格隔开的整数，代表一位选民的偏好列表（第一个整数是他最喜欢的候选人，最后一个是他最不喜欢的候选人）。每行中 1 到 $C$ 的每个整数恰好出现一次。

输出格式

对于每个测试用例，在一行中输出两个由空格隔开的整数。第一个整数是获胜者的 ID（从 1 到 $C$ 的数字），第二个整数是 1 或 2，表示该候选人是在第一轮还是第二轮获胜。

样例

样例输入 1

2
2 3
2 1
1 2
2 1
3 5
1 2 3
1 2 3
2 1 3
2 3 1
3 2 1

样例输出 1

2 1
2 2