As Valentines Day was approaching, some couples on the campus are upto some mischief and are sneaking around in the Campus Building. But the building has teachers roaming inside it. The teacher both blocks the way and will catch you if you fall into their line of sight. Also, everytime you take a step, each teacher turns by 90 degrees in clockwise direction. You can hide behind walls as teachers can't see through it or you can hide behind teachers too (from other teachers). Your aim is to help the couple reach the Goal from the Starting position without getting caught so that they can have some fun and spend some really good time.

(If you are seen by a teacher just when you reach the Goal, then also you are caught and your plans are ruined).

Input:

Input begins with an integer T, the number of mazes you'll explore. For each maze, there is first a line containing two integers, M and N, the height and width of the maze, respectively. The next M lines contain N characters each, describing the maze:

. (empty space)

'#' (wall) (without the quotes)

S (starting position)

G (goal)

< > ^ v (Line of sight of the teacher - Teacher can see in the direction pointed by the arrow)

The four symbols for Line of sight of the teacher signify teachers that are initially pointing left, right, up, or down respectively before you take your first step.

Output:

For the ith maze, print a line containing "Case #i: " followed by the smallest number of steps necessary to get to the exit without being seen by the teacher, or the string "impossible'' if there is no way to reach the goal safely.

Constraints:

1 ≤ T ≤ 100

1 ≤ M, N ≤ 100

Each maze will contain exactly one 'S' and exactly one 'G'.