Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting position to the goal.
An example of a maze:
S$###
$$#$$
$$$##
##$$G
It consists of S (starting position), # (walls), $ (road) and G (goal). In this example, it needs 7 steps from S to G. The mouse can move in four directions: up, down, left, and right. There may be more than one way to reach the goal, but the program only needs to print the smallest number of steps. If there is no way from S to G, then print -1.
The first line has an integer N (1 <= N <= 1000), which means the number of test cases. For each case, the first line contains two integers. The first and second integers R and C (3 <= R,C <= 500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R * C. The following R lines, each containing C characters, specify the elements of the maze.
Print the smallest number steps to reach the goal for each case. There is a newline character at the end of each line.