给定一个包含 $n$ 行 $m$ 列的矩阵 $A_0$。行和列均从 1 开始编号。矩阵中的元素为 0 或 1。记该矩阵第 $i$ 行第 $j$ 列的元素为 $A_0[i, j]$。

考虑一个无限矩阵序列 $A_k$。矩阵 $A_k$ ($k > 0$) 同样包含 $n$ 行 $m$ 列，它是矩阵 $A_{k-1}$ 对模 2 取余后的前缀和矩阵。形式化地，这意味着：

$$A_k[i, j] = \sum_{1 \le u \le i} \sum_{1 \le v \le j} A_{k-1}[u, v] \pmod 2$$

求最小的 $k > 0$，使得矩阵 $A_k$ 与 $A_0$ 逐元素相等。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ —— 矩阵 $A_0$ 的行数和列数。接下来的 $n$ 行包含矩阵各行的描述。每行包含 $m$ 个字符，每个字符均为 0 或 1。

数据范围

$1 \le n, m \le 10^6$ $n \times m \le 10^6$

输出格式

输出一个整数 $k$ —— 问题的答案。

样例

输入 1

1 1
1

输出 1

1

输入 2

4 2
00
01
10
11

输出 2

4