問題文

$H$ 行 $W$ 列のマス目が与えられます。 マス目の状態は $H$ 個の長さ $W$ の文字列 $S_1, S_2, ..., S_H$ で表されます。 $S_{i, j} =$ "#" ならば $i$ 行目 $j$ 列目のマスが黒く塗られていて、 $S_{i, j} =$ "." ならば $i$ 行目 $j$ 列目のマスが白く塗られていることを指します。

ここで、以下の条件を満たす盤面 $S$ を $K$ 次市松模様と定義します。

• $0 \leq x, y \leq 10 ^ {10}$ について、$\lfloor \frac{x}{K} \rfloor + \lfloor \frac{y}{K} \rfloor$ が奇数ならば $T_{x, y}$ は黒く塗られていて、偶数ならば $T_{x, y}$ は白く塗られているとする
• $1 \leq i \leq H, \ 1 \leq j \leq W$ を満たす任意の $(i, j)$ について、$S_{i, j}$ = $T_{i+p, j+q}$ となる $(p, q)$ の組み合わせ $(1 \leq p, q \leq K)$ が存在する

$S$ が $K$ 次市松模様であるとしたとき、条件を満たす最小の正整数 $K$ を出力してください。 条件を満たす $K$ が存在しないときは $-1$ を出力してください。

制約

• $1 \leq H, W \leq 1000$

入力

入力は以下の形式で与えられます。

出力

計算結果を一行に出力せよ。

サンプル

3 3
.#.
#.#
.#.

1

与えられたマス目は $1$ 次市松模様です。

4 5
#..##
.##..
.##..
#..##

2

与えられたマス目は $2$ 次市松模様です。

4 5
#....
.####
.####
.####

4

考えられる市松模様のうち、最も $K$ が小さいものは $4$ 次市松模様です。

2 3
..#
.#.

-1

与えられたマス目は市松模様ではありません。