Given a map, find the shortest time from S (Start) to G (Goal). The size of the map is specified by two integers: N and M. Each integer grid cell of the map has a mark, whose meanings are explained as follows.
1.'.' denotes an empty space,
2.'@' denotes a swamp,
3.'#' denotes a wall,
4.'S' denotes the start point, and
5.'G' denotes the goal.
There are only one S and only one G in the map. You can pass an empty space in 1 second, and pass a swamp in 2 seconds. But you cannot pass a wall cell. You are only allowed to move up, down, left, or right.
Here is an example: A map is of size 3×5, whose marks are specified as follows
S@..#
..#..
@@@@G
The shortest time from S to G is 7 seconds
The input file begins with an integer T (1 < T < 5000), indicating the number of test cases. Each test case begins with two integers N and M (0 < N < 100, 0 < M < 100), indicating the height and width of the map. In the following N lines, each line contains M characters describing the marks of the map.
For each case, output the shortest time you need from the start point to the goal. If there is no valid path from the start to the goal, output -1.