На планете PTZZZ живёт и работает n роботов. С незапамятных времён некоторые роботы дружат между собой, а некоторые — нет.

Ровно один раз в день некоторые роботы выходят на работу, а все остальные идут в парк развлечений и отдыхают. При этом на работу должен выйти хотя бы один робот. Определением того, кто будет работать, а кто отдыхать, занимается робот-директор. Работа настолько важна для роботов, что первый день, когда робот-директор принял решение, был назван Первым днём Мира.

Если окажется так, что в некоторый день на работу вышли в точности те же роботы, что и в какой-нибудь из предыдущих дней, то робот-директор заржавеет от горя. Кроме того, закон не позволяет роботу-директору отправлять на работу группу роботов, в которой какие-нибудь два робота не будут дружить между собой.

Робот-директор не хочет ржаветь от горя как можно дольше, поэтому он старается каждый раз отправлять на работу другую группу роботов. Однако, как легко понять, различных групп роботов всё же конечное число, поэтому роботу-директору в конце концов придётся заржаветь. От Вас требуется найти лишь номер дня, в который это произойдёт.

В первой строке записано целое число n, количество роботов на PTZZZ (1 ≤ n ≤ 50). В каждой из следующих n строк записано по n цифр 0 или 1. j-я цифра в i-й строке равна единице, если i-й и j-й роботы дружат между собой, и нулю в противном случае. Гарантируется, что i-я цифра в i-й строке равна нулю, а j-я цифра в i-й строке совпадает с i-й цифрой в j-й строке.

Выведите номер дня, в который робот-директор вынужден будет заржаветь от горя.