Minimum Moves: Grid Pathfinding Problem

Given a grid with N rows and M columns, you are required to determine the minimum number of moves needed to travel from the top-left corner to the bottom-right corner. The grid is represented by characters where a dot (.) denotes an empty cell and a hash (#) denotes a blocked cell. You can only move in the four cardinal directions: up, down, left, and right.

The start position is at the top-left cell (i.e. coordinates \( (0,0) \)) and the destination is at the bottom-right cell (i.e. coordinates \( (N-1, M-1) \)). The number of moves is defined as the number of transitions from one cell to a neighboring cell. If either the starting or the destination cell is blocked, or if no path exists, the answer should be \(-1\).

Hint: A Breadth-First Search (BFS) algorithm is well-suited to solve this problem since it finds the shortest path in an unweighted grid.

inputFormat

The first line of input contains an integer T, denoting the number of test cases. Each test case consists of:

1. A line containing two space-separated integers N and M — the number of rows and columns in the grid.
2. N lines each containing a string of length M composed of characters . and # representing the grid.

It is guaranteed that each grid is well-formed according to the given N and M.

outputFormat

For each test case, output a single line containing an integer which is the minimum number of moves required to reach the bottom-right cell from the top-left cell. If it is impossible to reach the destination, output \(-1\).

## sample

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

4
-1

</p>