D. Сжатие
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана двоичная матрица $$$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$$$-сжатие этой матрицы.

Обратите внимание: входные данные заданы в сжатом виде. Несмотря на это, лучше используйте быстрое считывание.

Входные данные

В первой строке записано одно число $$$n$$$ ($$$4 \le n \le 5200$$$) — количество строк и столбцов в матрице $$$A$$$. Гарантируется, что $$$n$$$ делится на $$$4$$$.

Далее следует описание матрицы. В каждой из $$$n$$$ следующих строк следуют по $$$\frac{n}{4}$$$ однозначных числа шестнадцатеричной системы счисления (то есть, эти числа могут задаваться либо как цифры от $$$0$$$ до $$$9$$$, либо как прописные латинские буквы от $$$A$$$ до $$$F$$$). Двоичная запись каждого из этих чисел задаёт очередные $$$4$$$ элемента матрицы в текущей строке. Например, если число равно $$$B$$$, то очередные четыре элемента матрицы равны 1011, а если число равно $$$5$$$, то очередные четыре элемента матрицы равны 0101.

Элементы в каждой строке задаются без пробелов.

Выходные данные

Выведите одно число: максимальное $$$x$$$, для которого возможно $$$x$$$-сжатие.

Примеры
Входные данные
8
E7
E7
E7
00
00
E7
E7
E7
Выходные данные
1
Входные данные
4
7
F
F
F
Выходные данные
1
Примечание

В первом примере задается матрица:

$$$11100111$$$
$$$11100111$$$
$$$11100111$$$
$$$00000000$$$
$$$00000000$$$
$$$11100111$$$
$$$11100111$$$
$$$11100111$$$

Довольно легко увидеть, что ответ равен $$$1$$$.