Problem E - Chomp

As you know, the Cookie Monster from Sesame Street is always interested in eating a lot of cookies. Recently, he even invented a game which, of course, was about... cookies. He wanted to have fun with Elmo, the furry red creature, while still being able to eat his favourite food. The game is for 2 players and he called it "Chomp". It starts with an MxN grid table of cookies. For example, it can be a 3x4 grid:

All the cookies are good, except the one in lower left position, which is a poisonous one, and nobody wants to eat it. The players take turns to choose one cookie from the table, eating it (that is, also removing it from the table), together with the cookies that are above it and to its right. For example, given the initial table above, these are 3 possible moves for the first player (eating and removing the selected cookies). Note there are also other possible moves.
or or

The game continues like that until one player is forced to eat the poisonous cookie. That player looses the game (nobody wants that cookie!)

For example, this would be a valid game in a 3x3 table, with player 2 losing because it can only eat the poisonous cookie:
Player 1 -> Player 2 -> Player 1 -> Player 2

You have to help Cookie Monster, because we wants to win all games against Elmo (and then challenge Oscar The Grouch, Kermit the Frog, Bert and Ernie).

The Problem

For a given table position of the Chomp game, if you have to tell if it is a winning position or not. That is, given that all players play the best moves, is it a guaranteed win for the player playing on that position. Or, in other words, no matter the other player responses, there is always a winning strategy that ensures the win for the player who is going to play first on that position.


In the first line of input comes an integer number C, indicating the number of Chomp positions (tables) to evaluate (1 ≤ C ≤ 10).

Then follow C tables, each one starting by a line with two space separated integers R and C, indicating respectively the number of rows and columns of the table (1 ≤ R,C < 10). After that come exactly R lines, each one with C characters, indicating the content of a valid table (where '.' means an empty position and 'C' means a cookie - the poisonous cookie is always on the lowest left position and is indicated by 'P').


For each table in the input you should output a line with the following format (where NUM is the table number in the input):

Case #NUM: winning position
Case #NUM: losing position
Of course the output should reflect the fact that the position is a winning one (guaranteeing a win) or not.

Sample Input

3 3
3 3
3 4
2 4

Sample Output

Case #1: losing position
Case #2: winning position
Case #3: winning position
Case #4: losing position

TIUP & CPUP 2007
Universidade do Porto
(30 de Maio de 2007)