Strange Billboard

A reconfigurable billboard is a regular grid of R x C square tiles. Each tile is white on one side and black on the other.

You change the picture by tapping tiles with a stick. Tapping a tile flips it to its other side (white becomes black, black becomes white). Because the tiles are packed tightly and their sides touch, tapping a tile also flips every tile that shares a whole side with it: the tiles directly above, below, to the left, and to the right. An interior tile therefore flips 5 tiles at once (itself plus 4 neighbors); tiles on an edge or corner have fewer neighbors and flip fewer tiles.

Given the starting pattern, find the smallest number of taps that turns every tile to its white side. Some patterns can never be cleared.

The input contains several billboard descriptions. Each description begins with a line holding two integers R and C (1 <= R, C <= 16), the number of rows and columns. The next R lines each contain exactly C characters: an uppercase X is a black tile and a dot . is a white tile. A blank line follows every board.

The input ends with a line containing two zeros (0 0) in place of the board size; this terminator is not a board and produces no output.

For each billboard, print exactly one line.

• If the board can be cleared, print You have to tap T tiles., where T is the minimum possible number of taps. The wording is fixed: always use the word tiles, even when T is 0 or 1.
• If it is impossible to make every tile white, print Damaged billboard. instead.