你正在制作一种巧克力曲奇，所用的机器拥有一个由单位正方形组成的矩形烤盘。你已经确定了曲奇的形状，它占据了该区域内的一些正方形。曲奇的每一个正方形区域都必须被“巧克力化”。

为了制作曲奇，你需要重复执行以下两个步骤：

1. 在一些单位正方形中放入曲奇面团。
2. 将曲奇面团暴露在浅层巧克力溶液中。任何没有被四个相邻正方形（上、下、左、右）完全包围的曲奇面团正方形都会被巧克力化。注意，位于烤盘边界上的任何面团正方形总是会被巧克力化。

以下示例展示了如何制作左侧所示形状 (s) 的曲奇：

(s) (a1) (a2) (b1) (b2) -X-X- -D-D- -C-C- -C-C- -C-C- XXXXX -DDD- -CCC- DCCCD CCCCC XXXXX -DDD- -CCC- DCCCD CCCCC -XXX- --D-- --C-- -DCD- -CCC- --X-- ----- ----- --D-- --C--

首先，你在 8 个正方形中放入面团 (a1)。第一次溶液暴露后，所有正方形都被巧克力化 (a2)。接着，你在另外 8 个正方形中放入面团 (b1)。第二次暴露使所有剩余正方形被巧克力化，完成了曲奇的制作 (b2)。

由于巧克力溶液很昂贵，你希望尽可能减少暴露次数。给定曲奇的形状，确定制作该曲奇所需的最少巧克力溶液暴露次数。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 1\,000$)，表示烤盘有 $n$ 行 $m$ 列单位正方形。

接下来的 $n$ 行，每行包含一个长度恰好为 $m$ 的字符串，其中每个字符要么是 “X”，表示该正方形被曲奇占据；要么是 “-”，表示一个空正方形。

曲奇的形状至少占据一个正方形。注意，该形状可能由多个不相连的部分组成。

输出格式

输出制作曲奇所需的最少巧克力溶液暴露次数。

样例

输入 1

5 5
-X-X-
XXXXX
XXXXX
-XXX-
--X--

输出 1

2

输入 2

4 5
--XXX
--X-X
X-XXX
XX---

输出 2

1

输入 3

5 5
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX

输出 3

3