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