Migrated from Lutece 1432 放箱子

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给出一个n*m的矩形仓库，仓库里有的位置已经被占用，剩下的位置可以用来放东西。

问这个仓库还可以放下多少个1*2或者2*1的箱子。

Input

输入有多组数据。

每组数据，第一行为两个整数n,m。

从第二行开始为一个n*m的矩形'.'表示为空,'*'表示已被占用。

1<=n,m<=100。

保证箱子总数不超过500。

Output

每组数据输出一行：包含一个整数最多能放下的箱子数.

Samples

4 4
*..*
.*..
....
**.*
4 3
...
.*.
**.
.*.

4
3

Resources

2016 UESTC Training for Graph Theory