提示: 欢迎访问OurACM平台。
Problem 2094 BlockGo

Accept: 14    Submit: 67
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

Perhaps you have played this game, BlockGo. It can be considered as a 6*6 grid, and there are several 1*n(n>1) blocks on the grid. All the blocks are either horizontal or vertical. If we assume the top left corner is (0,0), the only exit is always at the right of (2,5),(row 2, column 5), and the width of the exit is 1.

How to play?

Vertical blocks, can only move up or down.

Horizontal blocks, can only move left or right.

Move the red block to the right to exit, so as to win.

The silly boy LZX wants to know the minimum number of steps to win the given game. A step means that you can move a block legally at least 1 gird. At any time, any two blocks overlap is not allowed.

Input

The first line of input is n (n<30), the number of test cases.

Then n games follows. Before each game, there is an empty line.

For each game, it consists of 6*6 characters. Each character is either ‘.’ or a capital English letters. ‘.’ means empty, and the same letter makes a block. The red block always expressed as ‘A’. The exit is always at the right of (2,5).

It is guaranteed that each game has one red block, and different block has different colors.

Output

For each game, output the minimum number of steps to win the given game. The format should be the same as the sample output. It is guaranteed that you can win the game. Please separate each answers by an empty line.

Sample Input

2 ...... ....BB .AA..C .....C .....C .DDDEE BBB..C ..D.EC AADFE. ..GF.. ..G... ...HHH

Sample Output

Case 1: 4 Case 2: 6

Source

FOJ有奖月赛-2012年11月

Submit  Back  Status  Discuss