Illumination of the Park

In this problem, you are given a grid representing a park, where each cell is either empty (represented by a dot '.') or contains an obstacle (represented by a hash '#' symbol). Your task is to determine the minimum number of lights required to illuminate all the empty cells. When a light is placed in an empty cell, it illuminates all consecutive empty cells in its row and column until an obstacle or the boundary of the grid is encountered.

The illumination spreads in four directions: left, right, upward, and downward. Mathematically, if you place a light at position ( (i,j) ), it will illuminate every cell ( (i,k) ) for ( k ) such that ( grid[i][k] = '.' ) and ( k ) is in the contiguous segment, and similarly every cell ( (k,j) ) for the column.

You are also given multiple test cases in a single input. Each test case starts with two integers ( n ) and ( m ) (the number of rows and columns), followed by ( n ) lines representing the grid. A line containing "0 0" indicates the end of input. Your program should output one integer per test case, representing the minimum number of lights required.

inputFormat

The input is read from standard input (stdin) and consists of one or more test cases. Each test case begins with a line containing two integers ( n ) and ( m ), denoting the number of rows and columns respectively. This is followed by ( n ) lines, each containing a string of length ( m ) comprised of the characters '.' and '#'. The input terminates with a line "0 0" which should not be processed.

outputFormat

For each test case, output a single integer on a new line — the minimum number of lights required to illuminate all empty cells in the park.## sample

4 5
.###.
.#.#.
.#.#.
.###.
3 3
###
#..
###
2 2
##
##
0 0

3
1
0