daizhenyang's chess

As we know,daizhenyang likes playing chess,but he always lose,so one day,he invented a brand new chess game with the new rule.

The game is played on a chessboard with R rows and C columns, for a total of RC squares. Some of these squares are considered unlucky,so the chessman can't be moved to there.
The rule of this game is simple,diffrent from traditional chess,there is only a King on the chessboard beacuse daizhenyang thinks various chessmans leads to complex rule which makes poor daizhenyang hard to understand.
Also daizhenyang want's make the only chessman more powerful in order to become more unbeatable,The King is no longer the traditional weak king,it integrates the power of Guard,bishop,pawn,as well as knight.And the move range is not confined.It can move to anywhere which is considered lucky. So, according to the graph, the red king can move to 20 adjacent places.

And the aim of this game is simple too,The so-called King is placed in a random square of the chessboard which is considered lucky.Two players move the King alternately,in any move,the destination square must not be unlucky,and the king must never have been in the destination square before,which will causes dead loops.The first people who can't do a valid move lose.
daizhenyang is playing chess with another people,who is too shy to told his name.And daizhenyang moves first,he asks you--the genius programmer,for help.
please write a program to judge whether daizhenyang will win.Assume both player will play optimally.

The first line of input gives the number of cases, N.

N test cases follow. The first line of each case will contain two integers, R and C. The next R lines will contain strings of length C, representing the C squares of each row.(1<=R,C<=15) Each string will contain only the characters '.', '#' and 'K':
'#' means the square is considered unlucky;
'.' means the square is considered lucky, and unoccupied; and
'K' means the king is in that square at the beginning of the game.
There will be only one 'K' character in each test case.

For each test case, output one line containing "Case #X: " (where X is the case number, starting from 1) followed by "daizhenyang win" if daizhenyang wins, or "daizhenyang lose" if daizhenyang lose.

2
2 2
K.
.#

4 2
K#
.#
.#
.#

Case #1: daizhenyang lose
Case #2: daizhenyang win

In case 1,daizhenyang can do 2 choices,but no matter what he choose,the opponent will move to another,which makes daizhenyang unable to move.
In case 2,daizhenyang moves down,opponent moves down,daizhenyang moves down,he win!

2010 ACM-ICPC Multi-University Training Contest（2）——Host by BUPT