给定一个二进制矩阵 $$$A$$$,大小为 $$$n \times n$$$。让我们将给定矩阵的 $$$x$$$ 压缩表示为大小为 $$$\frac{n}{x} \times \frac{n}{x}$$$ 的矩阵 $$$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$$$ 压缩。
示例
输入 #1
8 E7 E7 E7 00 00 E7 E7 E7
输出 #1
1
输入 #2
4 7 F F F
输出 #2
1
注意
第一个示例对应于矩阵:
$$$11100111$$$
$$$11100111$$$
$$$11100111$$$
$$$00000000$$$
$$$00000000$$$
$$$11100111$$$
$$$11100111$$$
$$$11100111$$$
很容易看出这个例子的答案是$$$1$$$。