Наконец, пришло время проголосовать за нового президента, чему Вы очень рады. Вы знаете, что окончательные результаты могут быть объявлены через несколько недель, в то время как Вы сами не желаете долго ждать результатов. Каким-то образом Вам удалось получить список предпочтений для каждого избирателя (нас не интересует как Вы получили эту часть информации!). Каждый избиратель отсортировал всех кандидатов, начиная с наиболее предпочтительного и заканчивая наименее предпочитаемым. При голосовании избиратель голосует за кандидата, который стоит на первом месте в его списке предпочтений. Например, если имеется \textbf{5} кандидатов (пронумерованных от \textbf{1} до \textbf{5}), список предпочтений для одного избирателя \[\textbf{3, 2, 5, 1}, \textbf{4}\], текущими конкурирующими кандидатами при голосовании являются \textbf{2} и \textbf{4}, то избиратель проголосует за кандидата номер \textbf{2}. Следующие правила описывают выборный процесс: \begin{enumerate} \item Всего имеется \textbf{c }кандидатов (пронумерованных от \textbf{1} до \textbf{c}), и \textbf{v }избирателей (\textbf{v }всегда нечетно). \item Выборы могут проходить не более чем в два раунда. Все кандидаты принимают участие в первом раунде. Если кандидат получает более \textbf{50}\% голосов, он побеждает, иначе имеет место второй раунд, в котором участвуют только \textbf{2 }кандидата с наилучшими результатами. Кандидат, получивший большее количество голосов нежели его оппонент, становится новым президентом. \item Вы можете с уверенностью считать, что имеющиеся предпочтения никогда не приведут к ситуации, в которой второй и третий кандидаты в первом туре получат одинаковое количество голосов. \item Предпочтения избирателей одинаковы в обоих раундах, каждый избиратель голосует в каждом раунде только один раз за кандидата в соответствии со своими предпочтениями. \end{enumerate} По спискам предпочтений Вам следует написать программу, которая выяснит, какой кандидат победит и в каком раунде. \InputFile Первая строка содержит количество тестов \textbf{t }(\textbf{1 }≤ \textbf{t }≤ \textbf{100}). Первая строка каждого теста содержит два целых числа \textbf{c }и \textbf{v }(\textbf{1 }≤ \textbf{c}, \textbf{v }≤ \textbf{100}) - количество кандидатов и избирателей. Каждая из следующих \textbf{v }строк содержит по \textbf{c }целых чисел - предпочтения одного избирателя (первое число указывает на наиболее предпочтительного кандидата, последнее - на наименее предпочтительного). Каждое число от \textbf{1 }до \textbf{c }встречается в каждой строке только один раз. \OutputFile Для каждого теста вывести два числа в отдельной строке. Первое число - \textbf{ID }победившего кандидата (число от \textbf{1 }до \textbf{c}), второе число - \textbf{1} или \textbf{2} в зависимости от того, победил ли он в первом или во втором раунде.