問題文

各マスが白か黒で塗られた縦 $H$ マス横 $W$ マスのグリッド $X$ があります。グリッド $X$ の各マスの色は、# と . からなる $H$ 個の長さ $W$ の文字列 $S_1, \cdots, S_H$ で表され、$S_i$ の $j$ 文字目が # なら、上から $i$ 行目、左から $j$ 列目のマス $(i, j)$ は黒、. なら白を表します。

全てのマスの色が白である縦 $H$ マス横 $W$ マスのグリッド $Y$ に対して、$H$ 以下かつ $W$ 以下を満たす正整数 $k$ を選んで以下の操作を好きな回数だけ行うことでグリッド $X$ と一致させることが可能であるとき、グリッド $X$ は大きさ $k$ のスタンプで生成可能であるといいます。

(操作)
$1 \leq i \leq H-k+1$ かつ $1 \leq j \leq W-k+1$ を満たす整数のペア $(i, j)$ を選び、$i \leq l \leq i+k-1$ かつ $j \leq m \leq j+k-1$ を満たす全ての整数 $(l, m)$ について、グリッド $Y$ のマス $(l, m)$ の色が白ならば、そのマスを黒に塗り替える。

グリッド $X$ を生成可能なスタンプの大きさの最大値を求めてください。

入力

$H\ W$
$S_1$
$\vdots$
$S_H$

入力は以下の制約を満たす。

• $H, W$ は整数
• $1 \leq H \leq 2000$
• $1 \leq W \leq 2000$
• $S_i$ は # か . のみからなる長さ $W$ の文字列
• $S_i$ の $j$ 文字目が # であるような $(i, j)$ が少なくとも $1$ つ存在する。

出力

グリッド $X$ を生成可能なスタンプの大きさの最大値を出力してください。最後に改行してください。

サンプル

サンプル1

入力サンプルをコピー

入力

3 3
##.
###
.##

出力

2

グリッド $Y$ は最初以下のような状態です。

$k=2$ とした場合を考えます。

まず、$(1,1)$ を選んで操作を行います。すると、グリッド $Y$ は以下のようになります。

次に、$(2,2)$ を選んで操作を行います。すると、グリッド $Y$ は以下のようになり、グリッド $X$ と一致します。

$k\geq 3$ のとき、グリッド $X$ を生成することはできないので $2$ が答えです。

3 3
###
###
###

3

5 6
###.##
##.###
#####.
.###..
######

1