İquana
Parkda flora və fauna üçün genişmiqyaslı yenidənqurma işləri planlaşdırılıb. Təşkilatçılar parkın ərazisinin genişləndirilməsi, ekzotik heyvanların sayının artırılması və yeni volyerlərin tikilməsini planlaşdırıblar. Plan təsdiqləndikdən sonra inşaatçılar və zooloqlar işə başladılar.
Zooloqlar öz vəzifələrini yerinə yetirdilər: yeni zürafələr, çoxdan gözlənilən fillər, Karib adalarından iguanalar və bir çox digər heyvanlar və quşlar gətirdilər. Lakin inşaatçılar yeni volyerləri vaxtında tamamlaya bilmədilər, buna görə də gətirilən heyvanların müvəqqəti olaraq qəfəslərdə yerləşdirilməsinə qərar verildi.
Bu vəzifə də asan olmadı, çünki gətirilən heyvanlar üçün qəfəslər kifayət etməyə bilər. Bir qəfəsə yalnız uyğun heyvanlar yerləşdirilə bilər. Zooloqlar heyvanların uyğunluq cədvəlini tərtib etdilər və onu A = {a_ij} ölçüsü N×N olan matris şəklində təqdim etdilər. Əgər i və j nömrəli heyvanlar uyğundursa, onda a_ij = 0, əks halda a_ij = 1. Heyvanların təhlükəsiz yerləşdirilməsi üçün minimum qəfəs sayını müəyyən etmək lazımdır, belə ki, bütün qəfəslərdə yalnız bir-biri ilə uyğun heyvanlar yerləşdirilsin. Qəfəsdə bir, iki və ya daha çox heyvan ola bilər.
Giriş verilənləri
Giriş faylının ilk sətiri T – testlərin sayını göstərən bir ədəd ehtiva edir. Sonra T test təsvirləri gəlir. Hər bir testin təsviri N – heyvanların sayı (0 < N ≤ 100) olan bir sətirlə başlayır. Sonra N sətir, hər birində N ədəd olan heyvanların uyğunluq matrisi gəlir.
Çıxış verilənləri
Hər bir test üçün ayrı sətirdə bir tam ədəd çıxarın – heyvanların təhlükəsiz yerləşdirilməsi üçün lazım olan minimum qəfəs sayı.