eolymp
bolt
Try our new interface for solving problems
Problems

Игуана

Игуана

Time limit 5 seconds
Memory limit 256 MiB

В парке флоры и фауны затеяли масштабное переустройство. Организаторы запланировали расширение площади парка, увеличение количества экзотических животных и строительство новых вольеров. После утверждения плана строители и зоологи принялись за работу.

Зоологи со своей задачей справились: привезли новых жирафов, долгожданных слонов, игуан c карибских островов и многих других животных и птиц. А вот строители не успели достроить новые вольеры, поэтому привезенных животных было решено временно разместить в клетках.

Однако и эта задача оказалось непростой, так как клеток может не хватить для привезенных животных. А в одну клетку можно поместить только совместимых животных. Зоологи составили таблицу совместимости животных, представив ее в виде матрицы A = {a_ij} размером N×N. Если животные с номерами iи jсовместимы, то a_ij= 0, а если - нет, то a_ij = 1. Необходимо определить минимальное количество клеток для безопасного размещения животных, когда во всех клетках находятся только совместимые между собой животные. При этом в клетке может находиться одно, два и более животных.

Input data

Первая строка входного файла содержит одно число T – количество тестов. Далее идёт T строк описаний тестов. Описание каждого теста начинается со строки, содержащей число N - количество животных (0 < N100). Далее идет N строк по N чисел в каждой – матрица совместимости животных.

Output data

Для каждого теста в отдельной строке вывести одно целое число – минимальное количество клеток, необходимое для безопасного размещения животных.

Examples

Input example #1
2
5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
1
0
Output example #1
5
1
Source ACM ICPC 2012-2013, NEERC, Krasnojarsk