Ігуана
У парку флори та фауни запланували масштабне перепланування. Організатори вирішили розширити територію парку, збільшити кількість екзотичних тварин і збудувати нові вольєри. Після затвердження плану будівельники та зоологи розпочали роботу.
Зоологи виконали свою частину роботи: вони привезли нових жирафів, довгоочікуваних слонів, ігуан з Карибських островів та багато інших тварин і птахів. Однак будівельники не встигли завершити нові вольєри, тому було вирішено тимчасово розмістити привезених тварин у клітках.
Це завдання виявилося непростим, оскільки кліток може не вистачити для всіх привезених тварин. У кожну клітку можна помістити лише сумісних тварин. Зоологи склали таблицю сумісності тварин у вигляді матриці A = {a_ij} розміром N×N. Якщо тварини з номерами i та j сумісні, то a_ij = 0, а якщо ні, то a_ij = 1. Потрібно визначити мінімальну кількість кліток, необхідну для безпечного розміщення тварин, так щоб у кожній клітці знаходилися лише сумісні між собою тварини. У клітці може бути одна або більше тварин.
Вхідні дані
Перший рядок вхідного файлу містить одне число T — кількість тестів. Далі йдуть T рядків з описами тестів. Опис кожного тесту починається з рядка, що містить число N — кількість тварин (0 < N ≤ 100). Далі йдуть N рядків по N чисел у кожному — матриця сумісності тварин.
Вихідні дані
Для кожного тесту в окремому рядку вивести одне ціле число — мінімальну кількість кліток, необхідну для безпечного розміщення тварин.