CF1107D.Compression

You are given a binary matrix $A$ of size $n \times n$. Let's denote an $x$-compression of the given matrix as a matrix $B$ of size $\frac{n}{x} \times \frac{n}{x}$ such that for every $i \in [1, n], j \in [1, n]$ the condition $A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$ is met.

Obviously, $x$-compression is possible only if $x$ divides $n$, but this condition is not enough. For example, the following matrix of size $2 \times 2$ does not have any $2$-compression:

$01$

$10$

For the given matrix $A$, find maximum $x$ such that an $x$-compression of this matrix is possible.

Note that the input is given in compressed form. But even though it is compressed, you'd better use fast input.

给你一个大小为 $n \times n$ 的二进制矩阵 $A$。我们定义该矩阵的一个 $x$-压缩为一个大小为 $\frac{n}{x} \times \frac{n}{x}$ 的矩阵 $B$，使得对任意 $i \in [1, n],\, j \in [1, n]$，均满足条件

$$A[i][j] = B\left[\left\lceil \frac{i}{x} \right\rceil\right]\left[\left\lceil \frac{j}{x} \right\rceil\right].$$

显然，只有当 $x$ 整除 $n$ 时，$x$-压缩才可能实现；但该条件并不充分。例如，以下 $2 \times 2$ 矩阵不存在任何 $2$-压缩：

01
10

对于给定的矩阵 $A$，请找出最大的 $x$，使得该矩阵存在 $x$-压缩。

注意：输入以压缩形式给出。尽管已压缩，你仍应使用快速输入方式。

The first line contains one number $n$ ($4 \le n \le 5200$) — the number of rows and columns in the matrix $A$. It is guaranteed that $n$ is divisible by $4$.

Then the representation of matrix follows. Each of $n$ next lines contains $\frac{n}{4}$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $0$ to $9$ or as uppercase Latin letters from $A$ to $F$). Binary representation of each of these numbers denotes next $4$ elements of the matrix in the corresponding row. For example, if the number $B$ is given, then the corresponding elements are 1011, and if the number is $5$, then the corresponding elements are 0101.

Elements are not separated by whitespaces.

第一行包含一个整数 $n$（$4 \le n \le 5200$），表示矩阵 $A$ 的行数与列数。保证 $n$ 可被 $4$ 整除。

接下来是矩阵的表示。随后的 $n$ 行中，每行包含 $\frac{n}{4}$ 个一位十六进制数字（即这些数字可表示为数字 $0$ 至 $9$ 或大写拉丁字母 $A$ 至 $F$）。每个十六进制数字的二进制表示对应于该行中接下来的 $4$ 个矩阵元素。例如，若给出数字 $B$，则对应的元素为 $1011$；若给出数字 $5$，则对应的元素为 $0101$。

各元素之间不以空格分隔。

Print one number: maximum $x$ such that an $x$-compression of the given matrix is possible.

输出一个数字：最大的 $x$，使得给定矩阵存在 $x$-压缩。

The first example corresponds to the matrix:

$11100111$

$11100111$

$11100111$

$00000000$

$00000000$

$11100111$

$11100111$

$11100111$

It is easy to see that the answer on this example is $1$.

第一个示例对应的矩阵为：

$11100111$

$11100111$

$11100111$

$00000000$

$00000000$

$11100111$

$11100111$

$11100111$

容易看出，该示例的答案为 $1$。