Labyrinth Solver

You are given one or more labyrinths. Each labyrinth is represented as a 2D grid consisting of . (empty cell) and # (wall). Your task is to determine the minimum number of moves required to go from the top-left corner to the bottom-right corner of the grid. Moves are allowed in four directions: up, down, left, and right. If there is no valid path, output \( -1 \).

Note: The starting cell at the top-left and the destination cell at the bottom-right will be considered blocked if they contain a wall (#), in which case the answer is \( -1 \). Use Breadth-First Search (BFS) or any other method to determine the shortest path.

The problem may include multiple test cases within a single input.

inputFormat

The input begins with an integer \( T \) representing the number of labyrinths (test cases). For each test case, the first line contains two integers \( n \) and \( m \) representing the number of rows and columns of the labyrinth. This is followed by \( n \) lines, each containing a string of length \( m \), where . represents an open cell and # represents a wall.

Example:

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

outputFormat

For each labyrinth, print a single integer on a new line: the minimum number of moves required to reach the bottom-right cell from the top-left cell. If it is not possible to reach the destination, print \( -1 \).

## sample

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

4
-1

</p>