多连块（polyomino）是方格网中一组相连的单位正方形。下图展示了 4 个多连块的例子。

(a) (b) (c) (d)

如果一个多连块与任何垂直或水平线的交集都是一个线段，则称其为凸多连块。上图展示了两个凸多连块 (a) 和 (b)，以及两个非凸多连块 (c) 和 (d)。

如果两个正方形共享一条公共边，则称它们是相邻的。容易看出，对于凸多连块中的任意两个正方形，都可以通过仅使用两个方向，从一个正方形移动到另一个相邻的正方形，从而到达目标正方形。下图展示了多连块 (b) 的此类路径示例。

对于一个凸多连块 $P$，我们定义其“纠结度”（jinxiety）$J(P)$ 为满足以下条件的最小整数 $k$：从任意一个正方形出发，可以通过一条仅使用两个方向且转弯次数不超过 $k$ 次的路径到达任意其他正方形。例如，多连块 (a) 的纠结度为 1，多连块 (b) 的纠结度为 2。

给定一个凸多连块，你需要求出它的纠结度。

输入格式

输入文件包含多个测试用例。

每个测试用例包含两个整数 $h$ 和 $w$ —— 分别表示多连块描述的行数和列数 ($1 \le h, w \le 2000$)。

接下来的 $h$ 行，每行包含 $w$ 个字符，描述该多连块。每个字符要么是表示空方格的 “.”，要么是表示多连块正方形的 “#”。保证所描述的图形是一个凸多连块。

输入以一行 $h = w = 0$ 结束。输入文件中所有多连块描述的字符总数最多为 $4 \cdot 10^6$。测试用例数量最多为 $40\,000$ 个。

输出格式

对于每个测试用例，输出一个整数：该多连块的纠结度。

样例

样例输入 1

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

样例输出 1

1
2