Shortest Path in a Grid

You are given a grid with dimensions \(M \times N\), where each cell is either open (denoted by '.') or blocked (denoted by '#'). Your task is to determine the length of the shortest path from the top-left corner \((0, 0)\) to the bottom-right corner \((M-1, N-1)\). You can only move in four directions: up, down, left, and right. If there is no valid path, output \(-1\).

The problem consists of multiple test cases. For each test case, you are given the grid dimensions and the grid layout. Use an appropriate graph traversal algorithm (such as Breadth-First Search) to solve the problem.

inputFormat

The first line of the input contains a single integer \(T\) representing the number of test cases.

• For each test case:
• The first line contains two integers \(M\) and \(N\), denoting the number of rows and columns of the grid respectively.
• The following \(M\) lines each contain a string of length \(N\) consisting of characters '.' and '#', representing the grid.

outputFormat

For each test case, output a single line containing the length of the shortest path from the top-left corner to the bottom-right corner. If no path exists, output \(-1\).

## sample

4
3 3
..#
.#.
...
4 4
....
###.
....
.##.
3 3
..#
##.
...
2 2
..
..

4
6
-1
2

</p>