Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2292
Anti-bug before Chinese Valentine's Day

Time Limit: 2 Seconds      Memory Limit: 65536 KB

August 22, 2004 is Chinese Valentine's Day. popo's girlfriend qoqo asks popo to see beautiful star field with her. qoqo takes a fancy to a lawn at the back-hill. But as popo known, there are some bugs in the lawn. It's a feature that it has bug (-_-). So popo is planning to sprinkle pesticide in advance. And now popo needs your help to calculate how much pesticide needed at least to kill all the bugs on the lawn.


Two positive number n, m (2 <= n, m <= 8) in the first line of each test case, followed with n lines described the map of the lawn. In the map, 'o' indicates the grid which has bug in, '.' indicates the clean and clear grid. There are no other characters in the map.

n = m = 0 indicates the end of input.


A bottle of pesticide can kill all the bugs in a range of 2*2 grids, output the minimal number of bottles of pesticide needed.

Sample Input

2 2
3 3
0 0

Sample Output


Author: ZHENG, Jianqiang
Source: ZOJ Monthly, January 2005
Submit    Status