Shortest Path in a Maze

You are given a maze represented as a grid of characters. The maze contains exactly one starting position marked with an 'S' and one ending position marked with an 'E'. Walls are represented by '#' and free cells by '.'. You can move up, down, left, or right (no diagonal moves allowed). Your task is to determine the minimum number of moves required to reach 'E' from 'S'. If no such route exists, output -1.

Note: The answer is measured as the number of steps (moves) taken. Moving from one cell to an adjacent cell counts as one move.

The movement is allowed only if the cell is within the bounds of the maze and is not a wall.

The shortest path problem can be modeled using breadth-first search (BFS). The challenge is to carefully handle the input and output in a competitive programming fashion using stdin for input and stdout for output.

inputFormat

The input begins with an integer T representing the number of test cases. Each test case starts with two space-separated integers R and C indicating the number of rows and columns of the maze. The next R lines each contain a string of length C representing a row of the maze. It is guaranteed that each maze contains exactly one 'S' and one 'E'.

For example:

4
5 5
S....
.###.
..#..
.#...
...E.
5 5
S.#..
.#.#.
.###.
...#.
###.E
3 4
S...
....
...E
2 2
SE
..

outputFormat

For each test case, output a single line containing the minimum number of moves needed to reach from 'S' to 'E'. If no such path exists in the maze, output -1 instead.

## sample

1
2 2
SE
..

1

</p>