Петя решил зашифровать свой дневник, чтобы никто без его ведома не смог его прочитать. Для этого он воспользовался следующим шифром.
Он изготовил трафарет NxN клеток (N — четное), в котором вырезал
клеток так, что при наложении трафарета на лист бумаги четырьмя возможными способами (трафарет можно поворачивать, но нельзя переворачивать) каждая клетка листа видна ровно один раз.
Пример такого трафарета показан на рисунке ниже:

С помощью этого трафарета шифруется текст из N^2 символов следующим образом. Сначала в прорези трафарета вписываются первые (N^2)/4
букв шифруемого текста (буквы вписываются в вырезанные клетки по строкам сверху вниз, в каждой строке — слева направо). Например, если Петя шифрует слово ОЛИМПИАДА, то оно будет вписано в клетки следующим образом:

Далее трафарет поворачивается на 90 градусов по часовой стрелке, и в вырезанные клетки в том же порядке вписываются следующие (N^2)/4
букв шифруемого текста. И так далее. Если шифруемый текст состоит меньше, чем из N^2 символов, то (когда текст кончается) оставшиеся клетки остаются пустыми.
Например, если Петя шифрует текст ОЛИМПИАДА ПО ИНФОРМАТИКЕ 2006 ГОДА при помощи приведенного трафарета, то процесс шифрования будет устроен так. Как зашифровать слово ОЛИМПИАДА, мы уже показали. Для удобства здесь и далее пробел будем обозначать знаком подчеркивания. При втором прикладывании трафарета Пете удастся зашифровать _ПО_ИНФОР:

При третьем прикладывании трафарета Петя зашифрует МАТИКЕ_20:

При четвертом прикладывании трафарета Петя зашифрует 06_ГОДА. Остальные клетки окажутся пустыми (будем считать, что в них записан пробел, который мы обозначаем подчеркиванием):

После этого получившийся текст Петя выписывает в строчку:

О М0ЛП6И МОАТГ ИПОИКИДНАДАЕФ О 2РА 0

Для повышения надежности Петя решил зашифрованный текст зашифровать тем же методом с помощью того же трафарета еще раз, затем получившийся текст — еще раз и т.д. После нескольких повторов Петя с удивлением заметил, что зашифрованный текст совпал с исходным.
Напишите программу, которая для данного трафарета определит, после какого наименьшего количества процедур шифрования Петя получит исходный текст независимо от содержания текста?

Формат входных данных
Сначала во входном файле записано число N — размер трафарета (2≤N≤150). Затем идет N2 чисел (каждое из которых 0 или 1), описывающих трафарет. 1 обозначает вырезанную клетку, 0 — не вырезанную. Гарантируется, что данная последовательность описывает корректный трафарет для данного способа шифрования.
Формат выходных данных

В выходной файл выведите одно число — через какое минимальное количество повторов операции шифрования Петя получит исходный текст независимо от его содержания.

Будем считать, что Петя записывал не буквы, а числа от одного до N^2, и что полученный им шифр совпадает с последовательностью 1, 2, …, N^2. Пусть после применения шифровки к полученному тексту получается последовательность f(1), f(2), …, f(N^2), причем f(i)<>f(j) при i<>j. Последовательность f(1), f(2), …, f(N^2) будем называть перестановкой чисел от 1 до N^2. Рассмотрим ориентированный граф на вершинах, занумерованных числами от 1 до N^2, в котором есть ребро из i в j тогда и только тогда, когда f(i)=j (f переводит i в j). Ясно, что в каждую вершину входит и выходит ровно по одному ребру. Следовательно, наш граф разбивается на независимые циклы (докажите это). Обозначим длины этих циклов k1, k2, …, ks. Предположим теперь, что Петя применил к исходной последовательности перестановку f ровно X раз и вновь получил исходную последовательность. Это означает, например, что элементы, принадлежащие первому циклу “прошли” по нему целое число раз. Значит, X делится на любое ki. Поскольку нам нужно наименьшее такое X, то X=НОК(k1, k2, …, ks). Обратно, если взять такое X, то после применения перестановки f ровно X раз к исходной шифровке, получим ее же.
Таким образом, решение задачи разбивается на 2 этапа:
1) построение перестановки и вычисление длин ее циклов;
2) вычисление НОК.
Опишем вкратце реализацию этих этапов. Чтобы получить перестановку f нужно просто, следуя описанному в условии способу, зашифровать последовательность чисел 1, 2, …, N^2. Получится последовательность чисел f(1), f(2), … f(N^2). Чтобы получить последовательность k1, k2, … ks, нужно пройти по всем циклам описанного графа.
Осталось вычислить НОК. Для этого можно разложить на простые множители все ki. Далее для каждого простого числа pj выберем наибольшую степень mj, в которой оно входит в разложения чисел k1, k2, … ks. После этого нужно просто перемножить числа pj. Получится НОК, которое и будет ответом в задаче. Здесь есть еще одна проблема. При данных ограничениях результат может не поместиться в стандартных типах данных. Поэтому придется использовать длинную арифметику, то есть хранить результат в виде массива цифр и домножать его точно так же, как это делается в столбик.
Заметим, что в этой задаче сложность нахождения НОК с использованием предложенного алгоритма составляет порядка (n^2)*sqrt(n^2)=n^3 (чтобы разложить ki на простые множители надо перебирать все его делители от 2 до sqrt(n^2)). При данных в задаче ограничениях такой алгоритм работает достаточно быстро. Отметим, однако, еще один способ нахождения НОК, который работает быстрее.
На i-м шаге алгоритма будем получать ni=НОК(k1, k2, …, ki). Пусть ni-1 уже найдено. Тогда ni=(ni-1*ki)/НОД(ni-1,ki). Таким образом, задача сводится к нахождению НОД двух чисел. Для этого можно воспользоваться стандартным алгоритмом Евклида: НОД(a,b)=b, если a=0 и НОД(b,b mod a) иначе. Этот алгоритм работает логарифмическое по a*b время. Но поскольку в этой задаче приходится работать с длинными числами, а деление длинного числа на длинное достаточно трудно в реализации, целесообразно использовать так называемый бинарный алгоритм Евклида, а именно:
1) НОД(2*a,2*b)=2*НОД(a,b)
2) НОД(2*a+1,2*b)=НОД(2*a+1,b)
3) НОД(2*a+1,2*b+1)=НОД((2*a+1)-(2*b+1),2*b+1)=НОД(2*(a-b),2*b+1)
Случай 1) соответствует поиску НОДа двух четных чисел, 2) – четного и нечетного, 3) – случай двух нечетных, причем первое из них больше второго. Ясно, что этот алгоритм имеет оценку сложности асимптотически не хуже, чем стандартный, но здесь мы должны реализовывать лишь деление длинного числа на 2, что гораздо проще сделать.