Ігуана#3931
У парку флори та фауни запланували масштабне перепланування. Організатори вирішили розширити територію парку, збільшити кількість екзотичних тварин і збудувати нові вольєри. Після затвердження плану будівельники та зоологи розпочали роботу.
Зоологи виконали свою частину роботи: вони привезли нових жирафів, довгоочікуваних слонів, ігуан з Карибських островів та багато інших тварин і птахів. Однак будівельники не встигли завершити нові вольєри, тому було вирішено тимчасово розмістити привезених тварин у клітках.
Це завдання виявилося непростим, оскільки кліток може не вистачити для всіх привезених тварин. У кожну клітку можна помістити лише сумісних тварин. Зоологи склали таблицю сумісності тварин у вигляді матриці A = \{a_{ij}\} розміром N \times N. Якщо тварини з номерами та сумісні, то a_{ij} = 0, а якщо ні, то a_{ij} = 1. Потрібно визначити мінімальну кількість кліток, необхідну для безпечного розміщення тварин, так щоб у кожній клітці знаходилися лише сумісні між собою тварини. У клітці може бути одна або більше тварин.
Перший рядок вхідного файлу містить одне число — кількість тестів. Далі йдуть рядків з описами тестів. Опис кожного тесту починається з рядка, що містить число — кількість тварин (0 < N \leq 100). Далі йдуть рядків по чисел у кожному — матриця сумісності тварин.
Для кожного тесту в окремому рядку вивести одне ціле число — мінімальну кількість кліток, необхідну для безпечного розміщення тварин.
Приклад 1