На территории базы противника расположены N арсеналов, которые нужно уничтожить. Вы, Агент-070, имеете запас взрывчатки, достаточный для того, чтобы взорвать все N арсеналов по одному. Но при этом велик риск обнаружения.
Однако вам известно, что при взрыве каждого арсенала создаётся взрывная волна, которая может достичь других арсеналов и спровоцировать их взрыв. Эти арсеналы тоже будут создавать свои взрывные волны. В Центре вам выдали таблицу, в которой для каждого арсенала указано, какие другие арсеналы попадут под его взрывную волну.
Так как на минирование одного арсенала требуется время, а оно очень дорого, вам нужно заминировать как можно меньше арсеналов, чтобы, взорвав их, гарантированно уничтожить все арсеналы на базе.
В первой строке содержится число N — количество арсеналов на территории базы (1 ≤ N ≤ 100).
Далее дана таблица отношений: в N строках содержится по N символов, j-ый символ i-ой строки равен «1», если при взрыве i-го арсенала j-ый попадёт под его взрывную волну и «0» иначе.
Обратите внимание, что главная диагональ таблицы заполнена символами «0».
Выведите одно число — минимальное количество арсеналов, которое требуется заминировать для уничтожения всех арсеналов на базе.
3
000
100
100
2
3
010
001
000
1
