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.
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).
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 positionor
Case #NUM: losing positionOf course the output should reflect the fact that the position is a winning one (guaranteeing a win) or not.
4 3 3 ... ... P.. 3 3 CCC CCC PCC 3 4 .... C... PCCC 2 4 CCC. PCCC
Case #1: losing position Case #2: winning position Case #3: winning position Case #4: losing position