There are many kinds of Klotski game. "Unblock me" is the one very hot on cell phone. WWR loves it very much and is playing anytime. In this game, you can move blocks in a board whose size is 6*6. For simpler description, we label each block with capital letters, and we use '.' as an empty grid. So we can transform the image on the right into this:
123456 1 ...... 2 ...AB. 3 .CCAB.=> outside 4 DDEAB. 5 .FE... 6 .FGG..All blocks are rectangles and no one is a square. In each move, you can move only one block and stop wherever you like. Horizontal block can only move horizontally. Vertical block can only move vertically. The block cannot move out of the board or overlap other blocks. For example, block labeled with B can only move up 1 unit or down 1 or 2 units, cannot move left or right. Block C can only move left 1 unit. Block G can only move right 1 unit or 2 units. Both them cannot move up or down. The game's goal is to move red block (as described above, the red block is block C) outside the board. The exit of the board is always on the right of grid (3, 6). WWR wonders how to win the game in minimum number of moves. Can you help her?
The first line of the input is an integer T which stands for the number of test cases. Then T test cases follow. For each test case, there are 6 lines containing exactly 6 characters that describe the board. Then a line contains only one char, which indicates the label of the red block.
For each test case, output the minimum number of moves in one line. We assumed that all cases have solutions.
2 ...A.. ...A.. BB.A.. CCD.G. .FD.G. .F..G. B ...A.. ...A.. BB.A.. CCD.G. .FD.G. .FEEG. B
Sichuan University Programming Contest 2011 Final