A Puzzle Game

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)


Tower of the Sorcerer is a cross between a puzzle game and an RPG.
The story is saving the princess who was locked in the magic tower; it is the such story as you have heard the other day. But the fact is that this story isn't related to this game at all. Why? You will know the reason when you play this game. As the content of this is RPG, there is the side like a puzzle. Please play this without hurry combining with training of brain.

To save the princess you must go up the floors. You fight the bad guys and get keys to open doors. You have a health meter and you can gold coins and experience to increase defensive power, offensive power, and health. The levels are not randomly generated so the game will be the same every time you play.
Is it a complex game? Let’s take it easy. Imagining that you have met the princess and gone back to ground floor, your mission is going to the destination position of the maze on ground floor. This is a two-dimensional maze composed of square cells which may or may not be filled with rock. You can move north, south, east or west one cell at a step. You can move north, south, east or west one cell at a step. There are some locked doors (the number of them not more than 10). Maybe you could open some of them to go to the destination place. Luckily, many keys are hidden in the maze. These keys can open any doors, but each of them can be only used once.


The first line of input contains a single positive integer. This is the number of mazes that follow. Each maze description starts with a line containing one integer r (r <= 10) representing the number of rows of the maze. The number of columns equals the number of rows of the maze
Following this are r lines each containing r characters. Each character describes one cell of the maze. A cell full of rock is indicated by a '*' and an empty cell is represented by a '.'. Your starting position is symbolized by 'S', the destination position by 'E', the position where is hidden a key by 'K' and the position of the locked door by 'L'.


For each maze in the input, first print the number of the maze, as shown in the sample output. Then, if it is possible to go to the destination position, print "Yes". Otherwise, output "No"

Sample Input

3 2 *E *S 2 *E S* 3 E.. **L SK.

Sample Output

Case 1: Yes Case 2: No Case 3: Yes




2010 ACM-ICPC Multi-University Training Con