Петя вирішив зашифровати свій щоденник, щоб ніхто без його відома не зміг його прочитати. Для цього він скористався наступним шифром. Він виготовив трафарет \textbf{N}×\textbf{N} клітинок (\textbf{N} --- парне), у якому вирізав \textbf{N^2/4} клітинок так, що при накладанні трафарету на аркуш паперу чотирма можливими способами (трафарет можна повертати, еле не можна перевертати) кожна клітинка аркуша видна рівно один раз. Приклад такого трафарету показано на рисунку нижче: \includegraphics{https://static.e-olymp.com/content/9d/9d2bbc0557a3b46add86def3b35ffd8105149427.jpg} При допомозі цього трафарету шифрується текст з \textbf{N^2} символів наступним чином. Спочатку у прорізи трафарету вписуються перші \textbf{N^2/4} літер тексту, що шифрується (літери вписуються у вирізані клітинки по рядкам зверху до низу, а у кожному рядку --- зліва праворуч). Наприклад, якщо Петя шифрує слово "\textbf{ОЛИМПИАДА}", то воно буде вписано у клітинки наступним чином: \includegraphics{https://static.e-olymp.com/content/05/055e8f0e1fc2f4965f01e729abb6e29e262471d3.jpg} Далі трафарет повертається на \textbf{90} градусів за годинниковою стрілкою, і у вирізані клітинки у тому ж порядку вписуються наступні \textbf{N^2/4} літер тексту, що шифрується. І так далі. Якщо текст, що шифрується, складається менше, ніж з \textbf{N^2} символів, то (коли текст закінчується) клітинки, що залищились, залишаються порожніми. Наприклад, якщо Петя шифрує текст "\textbf{ОЛИМПИАДА ПО ИНФОРМАТИКЕ 2006 ГОДА}" при допомозі наведеного трафарету, то процес шифрування буде влаштовано так. Як зашифрувати слово "\textbf{ОЛИМПИАДА}", ми вже показали. Для зручності тут і далі пропуск будемо позначати символом підкреслювання. При другому прикладанні трафарету Петі вдасться зашифрувати "\textbf{_ПО_ИНФОР}": \includegraphics{https://static.e-olymp.com/content/c7/c798ca281e54e98e9f5600778666eb8b48295ba3.jpg} При третьому прикладанні трафарету Петя зашифрує "\textbf{МАТИКЕ_20"}: \includegraphics{https://static.e-olymp.com/content/0b/0b00ed0f447b5a9165d9e94f77b1201b9f539c3f.jpg} При четвертому прикладанні трафарету Петя зашифрує "\textbf{06_ГОДА}". Інші клітинки виявляться порожніми (будемо вважати, що в них записано пропуск, який ми позначаємо підкреслюванням): \includegraphics{https://static.e-olymp.com/content/49/496e059b63a98e0593a0183614465bbcbeb39857.jpg} Після цього отриманий текст Петя виписує у рядок: \textbf{О М0ЛП6И МОАТГ ИПОИКИДНАДАЕФ О 2РА 0} Для підвищення надійності Петя вирішив зашифрований текст зашифрувати тим же методом при допомозі того ж трафарету ще раз, потім отриманий текст --- ще раз і т.д. Після декількох повторень Петя з подивом помітив, що зашифрований текст співпав з початковим. Напишіть програму, яка для заданого трафарету визначить, після якої найменшої кількості процедур шифрування Петя отримає початковий текст незалежно від змісту тексту? \InputFile Спочатку у вхідному файлі записано число \textbf{N} --- розмір трафарету (\textbf{2} ≤ \textbf{N} ≤ \textbf{150}). Далі йде \textbf{N^2} чисел (кожне з яких \textbf{0} або \textbf{1}), які описубть трафарет. \textbf{1} позначає вирізану клітинку, \textbf{0} --- не вирізану. Гарантується, що задана послідовність описує коректний трафарет для заданого способу шифрування. \OutputFile У вихідний файл виведіть одне число --- через яку мінімальну кількість повторень операції шифрування Петя отримає початковий текст незалежно від його змісту.