Вам дана двоичная матрица \(A\) размера \(n \times n\). Обозначим \(x\)-сжатие данной матрицы как матрицу \(B\) размера \(\frac{n}{x} \times \frac{n}{x}\), такую, что для всех \(i \in [1, n], j \in [1, n]\) выполняется условие \(A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]\).
Очевидно, \(x\)-сжатие возможно только в том случае, если \(x\) является делителем \(n\), но этого недостаточно. К примеру, у этой матрицы \(2 \times 2\) нет \(2\)-сжатия:
\(01\) \(10\) Для заданной матрицы \(A\) найдите максимальное \(x\), для которого возможно \(x\)-сжатие этой матрицы.
Обратите внимание: входные данные заданы в сжатом виде. Несмотря на это, лучше используйте быстрое считывание.
Выходные данные
Выведите одно число: максимальное \(x\), для которого возможно \(x\)-сжатие.
Примечание
В первом примере задается матрица:
\(11100111\) \(11100111\) \(11100111\) \(00000000\) \(00000000\) \(11100111\) \(11100111\) \(11100111\) Довольно легко увидеть, что ответ равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
E7
E7
E7
00
00
E7
E7
E7
|
1
|
|
2
|
4
7
F
F
F
|
1
|