G	NEXT generation contest - 4	Time Limit – 5 secs
	Guards, Imbecile Guards

You have a square maze of size N x N. You begin from a source cell and start your journey in hope of reaching the target cell in minimum number of moves. You can move to new cell if it shares an edge with the current cell you are standing on. The minimum moves required aren’t always the Manhattan distance as there are few obstacles placed on certain places of the maze. You have to avoid those obstacles in your path. In addition to the obstacles, there are more impediments in the form of guards. The guards, however, aren’t that clever and they are also short-sighted. Initially every guard monotonously walks to the right. If it encounters an obstacle or reaches the end of the maze (last column) it turns left and starts walking. It walks left until it reaches an obstacle or the end (first column) when it changes direction to the right and starts walking. Every guard moves 1 cell per unit time. Your speed is also 1 cell per unit time. In every unit time, you can either make a move or stay in the same position. Staying in the same position also counts as a move.

You are caught by a guard if both of you land on the same cell at the same time or if you bump into each other during a move. In the latter case, you are caught in between the cells.

Every cell of the maze will be represented by one of the following:

S – Starting Cell.

T – Target Cell.

# - An Obstacle

X – A Guard

. – An Empty Cell

There will be at most 3 guards in a maze and all of them will be situated in different rows.

An example of the movement of a guard for first 6 seconds of its locomotion:

...... ...... ...... ...... ...... ...... ......
...... ...... ...... ...... ...... ...... ......
.#.X.. .#..X. .#...X .#..X. .#.X.. .#X... .#.X..
...... ...... ...... ...... ...... ...... ......
0 1 2 3 4 5 6

Input

The input file starts with an integer T(T<50) that indicates the number of test cases. Each case starts with a positive integer N(N<10). The next N lines contain N characters each that fill up the maze. There will be exactly one S character and one T character. There will be no more than 3 X characters in the maze.

Output

For each input, output the case number followed by the minimum number of moves required. If it is impossible to reach the target, output -1 instead.

Sample Input	Output for Sample Input
2 4 S... #### .... X.#T 5 T.X.. ..#.. .#S#. ..... .....	Case 1: -1 Case 2: 7

ProblemSetter: Sohel Hafiz
Special Thanks: Vinay Singh