Game of Tiles

The Game of Tiles is a two-player game played on a rectangular board of $R$ rows and $C$ columns of square cells called tiles. At the start of the game some tiles may be painted black and the rest are white. Player 1 and Player 2 then take turns; the first player who cannot make a valid move loses.

Player 1 moves first. The first move consists of choosing a white tile and writing the number $1$ on it. Each subsequent move $i$ consists of writing the number $i$ on an unused white tile that is horizontally or vertically adjacent (never diagonally) to the tile numbered $i-1$. Thus Player 1 always writes the odd numbers and Player 2 always writes the even numbers.

Given the initial configuration of the board, determine which player wins if both play optimally.

The input contains several test cases and is read until end of file. Each test case is described using several lines. The first line contains two integers $R$ and $C$ ($1 \le R, C \le 50$), the number of rows and columns of the board. Each of the next $R$ lines contains a string of $C$ characters describing one row of the initial board: the character '.' denotes a white tile and the uppercase letter 'X' denotes a black tile. In every test case at least one tile is white.

For each test case, output a single line containing the number of the player (1 or 2) who wins the game when both play optimally.