Shortest Path in Maze

You are given several mazes. Each maze is represented by an n x m grid where each cell is either an open space denoted by . or a wall denoted by #. Your task is to find the shortest path from the top-left corner (cell $(0,0)$) to the bottom-right corner (cell $(n-1, m-1)$) using only moves in the four cardinal directions (up, down, left, right) and without passing through any walls.

If a path exists, output its length. Otherwise, output -1.

Input/Output via Standard I/O: The input is read from stdin and the output is printed to stdout.

Note: The distance is defined as the number of moves between cells.

The problem can be formally stated as finding the minimum number of moves required to reach the destination, which can be written in LaTeX as:

$$\min\{d\,|\,\text{there exists a path from }(0,0)\text{ to }(n-1,m-1)\text{ of length }d\}. $$

inputFormat

The first line of input contains an integer T representing the number of test cases. For each test case, the first line contains two integers n and m separated by a space representing the number of rows and columns of the maze. The following n lines each contain a string of length m that represents the maze.

Example:

3
3 3
...
.#.
...

outputFormat

For each test case, output a single integer which is the length of the shortest path from the top-left corner to the bottom-right corner. If no such path exists, output -1. Each answer should be printed on a new line.

## sample

1
1 1
.

0

</p>