Background

不难发现，豆豆能从很多事情中去思考数学，于是豆豆父母决定让他去练习射击，这是项需要集中注意力的运动，相信能够让豆豆暂时脱离数学。学习射击的第一天就让豆豆产生了浓厚的兴趣，射击的靶子是大饼圆，射击枪的子弹近似圆柱，为什么要圆的不能是其他的形状呢，于是豆豆开始构思，设计了这样一个好玩的问题：

$N*M$ 的方形格子靶子，每个格子有两种状态凸或者凹（如下图浅色表示凹，深色表示凸）

现在用一个十字横截面的子弹（填充黑色部分）去射击，被射中的小格子凹变凸，凸变凹，子弹放大后的横截面如下图

这种子弹最多可以覆盖$5$个格子，如图打完后，$5$个格子凹凸状态发生了变化

请问最少需要几次射击使靶子中所有小格子都呈现凹的状态。

注意：子弹中心点如果打到四个角上则只会影响 $3$个格子，如下图黑色格子表示被子弹中心点正好击中左上角后覆盖的$3$个格子，如果打到除四个角的边界上，则会影响到 $4$ 个格子，如下图右侧的 $4$个黑色格子所示，这是子弹中心点打中第 $3$行第 $6$列时的覆盖情况。（也就是说子弹超出靶子部分不起效）

.

Input

第一行两个用空格隔开的数字 $N$和 $M(1<=N,M<=17)$

接下来 $N$行描述靶子中小格子的状态，‘X’表示凸，‘.’表示凹。

Output

输出所需要的最少射击次数

注意：输入数据保证有解

Samples

5 5
XX.XX
X.X.X
.XXX.
X.X.X
XX.XX

5

8 9
..XXXXX..
.X.....X.
X..X.X..X
X.......X
X.X...X.X
X..XXX..X
.X.....X.
..XXXXX..

25

Limitation

【数据范围】

对于 $30\%$的数据，$1<=N,M<=4$

对于 $70\%$的数据，$5<=N,M<=17$