В парке флоры и фауны затеяли масштабное переустройство. Организаторы запланировали расширение площади парка, увеличение количества экзотических животных и строительство новых вольеров. После утверждения плана строители и зоологи принялись за работу. Зоологи со своей задачей справились: привезли новых жирафов, долгожданных слонов, игуан c карибских островов и многих других животных и птиц. А вот строители не успели достроить новые вольеры, поэтому привезенных животных было решено временно разместить в клетках. Однако и эта задача оказалось непростой, так как клеток может не хватить для привезенных животных. А в одну клетку можно поместить только совместимых животных. Зоологи составили таблицу совместимости животных, представив ее в виде матрицы \textbf{A = \{a_ij\}} размером \textbf{N×N}. Если животные с номерами \textbf{i}\textit{ }и \textbf{j}\textit{ }совместимы, то \textbf{a_ij} \textbf{= 0}, а если - нет, то \textbf{a_ij = 1}. Необходимо определить минимальное количество клеток для безопасного размещения животных, когда во всех клетках находятся только совместимые между собой животные. При этом в клетке может находиться одно, два и более животных. \InputFile Первая строка входного файла содержит одно число \textbf{T} -- количество тестов. Далее идёт \textbf{T} строк описаний тестов. Описание каждого теста начинается со строки, содержащей число \textbf{N} - количество животных (\textbf{0} < \textbf{N} \textit{≤ }\textbf{100}). Далее идет \textbf{N} строк по \textbf{N} чисел в каждой -- матрица совместимости животных. \OutputFile Для каждого теста в отдельной строке вывести одно целое число -- минимальное количество клеток, необходимое для безопасного размещения животных.