题目描述

给你一个大小为 $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[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil] 。 $$

显然，只有当 $x$ 除以 $n$ 时， $x$ 压缩才是可能的，但这个条件还不够
例如，下面这个大小为 $2 \times 2$ 的矩阵就不存在任何 $2$ 压缩：

$$\begin{bmatrix} 0 & 1\\ 1 & 0 \end{bmatrix}$$

对于给定矩阵 $A$ ，求最大值 $x$ ，使得该矩阵可以进行 $x$ 压缩。

输入格式

第一行包含一个数字 $n$ ( $4 \le n \le 2000$ ) - 矩阵 $A$ 的行数和列数。可以保证 $n$ 可以被 $4$ 整除

矩阵的表示方法如下。接下来的 $n$ 行中的每一行都包含 $\frac{n}{4}$ 个十六进制数字（即这些数字既可以用 $0$ 至 $9$ 的数字表示，也可以用 $A$ 至 $F$ 的大写拉丁字母表示）。这些数字的二进制表示法分别代表相应行中矩阵的下一个 $4$ 元素。
例如，如果给出的数字是 $B$ ，那么对应的元素就是 1011；如果数字是 $5$ ，那么对应的元素就是 0101。 元素之间不用空格隔开。

输出格式

打印一个数字：最大 $x$ ，从而可以对给定矩阵进行 $x$ 压缩。

样例1

8
E7
E7
E7
00
00
E7
E7
E7

1

样例2

4
7
F
F
F

1

第一个例子与矩阵相对应：

$$\begin{bmatrix} 1& 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1& 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1& 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0& 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1& 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1& 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1& 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \end{bmatrix} $$

不难看出，这个例子的答案是 $1$ 。