Minimum Steps in Grid Navigation

You are given a rectangular grid of size \(N \times M\). Each cell in the grid is either free (denoted by a dot .) or blocked (denoted by a hash #). Your task is to calculate the minimum number of steps required to travel from the top-left corner (cell \((0, 0)\)) to the bottom-right corner (cell \((N-1, M-1)\)) by moving up, down, left, or right. If there is no valid path, output \(-1\).

Note: The number of steps is defined as the number of moves you make. For example, if the starting and ending positions are the same, then the minimum steps required is 0.

The problem can be formally expressed using the following notation: Given a grid \(G\) with \(N\) rows and \(M\) columns, determine the minimum \(k\) such that there exists a sequence of valid moves \(\{(r_i, c_i)\}_{i=0}^{k}\) with \((r_0, c_0) = (0, 0)\) and \((r_k, c_k) = (N-1, M-1)\), and for each consecutive pair \((r_i, c_i)\) and \((r_{i+1}, c_{i+1})\), \(|r_i - r_{i+1}| + |c_i - c_{i+1}| = 1\). If no such sequence exists, the answer is \(-1\).

inputFormat

The first line of input contains an integer \(T\), the number of test cases.

Each test case is described as follows:

• The first line contains two space-separated integers \(N\) and \(M\) indicating the number of rows and columns, respectively.
• The next \(N\) lines each contain a string of length \(M\) consisting of characters . (empty cell) and # (obstacle), representing the grid.

All input is read from standard input (stdin).

outputFormat

For each test case, output a single integer: the minimum number of steps required to reach the bottom-right corner from the top-left corner. If no valid path exists, output \(-1\).

Each result should be printed on a new line to standard output (stdout).

## sample

4
1 1
.
1 1
#
3 3
...
.#.
...
3 3
.#.
###
...

0
-1
4
-1

</p>