Maze Navigation Challenge

Jerry is participating in a maze competition. The challenge is set on a grid with (M) rows and (N) columns, where each cell is either walkable (represented by a '.') or blocked by a wall (represented by a '#'). Jerry starts at the top-left corner ((1, 1)) and must reach the bottom-right corner ((M, N)). He can move in four directions: up, down, left, and right. Your task is to compute the minimum number of steps required for Jerry to complete his journey. If no valid path exists, output (-1).

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T), the number of test cases. Each test case consists of a line with two integers (M) and (N) (the number of rows and columns), followed by (M) lines, each containing a string of length (N) representing the maze. Walkable cells are denoted by a '.' and walls by a '#'.

outputFormat

For each test case, output a single integer on a new line: the minimum number of steps from the cell ((1, 1)) to ((M, N)). If it is impossible to reach the destination, output (-1).## sample

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

6