Shortest Path in Grid

Given an n×m grid where each cell is either empty (represented by .) or blocked (represented 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)). You can move in four directions: up, down, left, or right. The path can only traverse through empty cells. If no valid path exists, output -1.

Note: You may refer to the Manhattan distance formula $d=|x_2-x_1|+|y_2-y_1|$ for an intuitive understanding of grid distances.

inputFormat

Input is taken from standard input (stdin). The first line of the input contains an integer $T$, denoting the number of test cases. For each test case, the first line contains two integers $n$ and $m$ representing the number of rows and columns respectively. This is followed by $n$ lines, each containing a string of exactly $m$ characters which describes one row of the grid.

outputFormat

For each test case, output one line containing a single integer denoting the minimum number of moves required to reach from the top-left to the bottom-right corner. If it's impossible to reach, print -1.## sample

2
3 4
....
.*..
....
4 4
*..*
.*.*
.*.*
*..*

5
-1