Rosswell wolves and cows P69326

It is unfortunate that, due to the messy state of the world we live in, the publication of the memories of Lieutenant Coronel Sargent Major John R. Smith III, Phd, MD, MotU by the United States Air Force has remained mostly unnoticed by the public.

Officer Smith was in charge of the Roswell Army Air Field during the 1940s, and in his memories he finally confirms what conspiracy theorists have suspected during the last decades: the Roswell incident was indeed an extra-terrestrial encounter—albeit of a different kind than expected.

According to Smith, after following the trajectory of a falling object on the sky, soldiers of the United States Air Force encountered the debris of a space ship. The search for the pilot ended in the most confusing way: the cows that grazed in the area had instinctively started chasing and corralling the confused alien, which turned out to be a wolf-like creature, across the checkered corn and soy fields of New Mexico. The traveller was completely surrounded by the animals and could not escape when the soldiers arrived.

Input

Input consists of several cases, each one starting with the dimensions H and W of the area around Roswell, which can be represented as a chess board. Follow H lines, each containing W characters. A dot corresponds to an empty position, whereas ‘C’ corresponds to a cow. All cows will be in the white squares of the board, with the top left one being white. Assume that H and W are between 1 and 32, and that there are at most 12 cows on each board.

Cows and the wolf move by turns, never leaving the board. In the first turn, the alien wolf can land in any white square which is not occupied by a cow. There will always be at least one such square.

Afterwards, in each turn for the cows, one of them must move to a diagonally adjacent square of the row above their current position which is not occupied by the wolf or another cow. If no cow can move, their turn is skipped and the wolf moves again.

In subsequent turns for the wolf, it must move to one of the four diagonally adjacent squares that is not occupied by a cow. If all four positions are occupied, the wolf has been captured. The wolf succeeds to escape if it reaches a square in the bottom row.

Output

For each case, print the number of landing squares for the alien wolf from where there exists a winning sequence for it. Do not assume any strategy by neither wolf nor cows.