magic-circuit

Last year iElectro has given a circuit deigning problem , in which participants will have to prepare a grid of bulbs such that ,if you select a particular bulb in the grid to toggle (if bulb is ON you turn it OFF and vice versa),then the bulb itself and its neighbouring (up,down,left,right) bulbs will also get toggled.

The Winners of that competition, has a challenge for all you programming geeks. Now you are given the same grid with some random bulbs on and off, and your task is to find the minimum number of choices you could make to lit all the bulbs in the grid. 

Input:
Description of each grid starts with a line of two space separated integers n and m representing number of rows and columns of the grid respectively. Next n lines each with m characters represents the grid. 

‘X’ in the grid represents the bulb which is OFF.

‘.’ In the grid represents the bulb which is ON.

Each description of the grids will be separated by a line. Test case ends with the line “0 0”.

1 ≤ n,m ≤ 15

Output:
For each grid print the minimum number of choices made to turn on all the lights in a new line, print -1 if not possible to do so.

SAMPLE INPUT
3 3
.X.
XXX
.X.

1 5
...XX

0 0

SAMPLE OUTPUT
1
1

Explanation

Case 1: By Toggling the light at position (2,2) all the lights will turn on.
Case 2: By toggling the light at position (1,5) all the lights will turn on.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: