Jump the Chess

Time Limit: 1 Second    Memory Limit: 32768 KB

Now give you a chessboard of "Jumping Chess" and there are several chesses on the chessboard. Your task is to compute the minimal steps for the given chess jumping from the start point to the destination.

If you have never played this game, I will tell you some rules of "Jumping Chess". The only thing you must know is that what means one step.

Each step, you can only choose "Move" the chess or "Jump" the chess.

If you choose "Move" the chess, you can only move the chess to the adjacent vacant lattice (adjoins the lattice which the chess originally occupied).

If you choose "Jump" the chess, you can jump the chess endlessly. But you must obey the "Jumping" rules. Each "Jump", you can only jump the chess in a line and jump over exactly one occupied lattice (no other vacant lattice). We can consider each "Jump" as two "Moves" in a line, which the first "Move" is from its original lattice to a occupied lattice and the second "Move" is from the occupied lattice to a vacant lattice (tow moves must be in a line).

Now lets see an example here (see the figure above). We want to move the given chess to the destination. The minimal steps is 2 steps, which the first step is to "Move" the chess and the second step is to "Jump" the chess.

(Notice: the example is just an example of how to jump the chess, and the chessboard size of this problem is smaller than the size of the figure above.)

Input

The input file begins with an integer T, indicating the number of test cases. Each test case begins with a blank line. Then the following 13 lines describe the chessboard. 'o' denotes a vacant lattice, '*' denotes a lattice occupied by a chess, 'S' denotes the given chess and it's start point, 'E' denotes the destination (also a vacant lattice).

Output

For each chessboard, first output the number of the test case (`Chessboard #1:', `Chessboard #2:', etc.) in a line of its own.

If it is possible for the given chess to get to the destination, print a line containing the minimal steps for the given chess jumping from the start point to the destination. Adhere to the output format shown in the sample below.

If the given chess can't jump to the destination, output a line containing the statement `Impossible.'

Separate the output of different cases by a blank line.

Sample Input

2

E
 * *
 o o o
o o o o * o o o o o
 o o o o o o o o o
 o o o o * o o o
 o o o * o o o
 o o o S o o o o
 o o o o o o o o o
o o o o o o o o o o
 o o o
 o o
 o

E
 * *
 * o *
o o o o o o o o o o
 o o o o o o o o o
 o o o o o o o o
 o o S o o o o
 o o o o o o o o
 o o o o o o o o o
o o o o o o o o o o
 o o o
 o o
 o

Sample Output

Chessboard #1:
2 steps.

Chessboard #2:
Impossible.

Submit

Source: ZOJ Monthly, December 2003