Maze Shortest Path

You are given an \(N\times N\) grid representing a maze. Each cell of the grid is either empty (denoted by .) or blocked by a wall (denoted by #). Your goal is to determine the length of the shortest path from the top-left cell (cell \((0,0)\)) to the bottom-right cell (cell \((N-1,N-1)\)). You can move in four directions: up, down, left, and right. You are not allowed to move diagonally or pass through walls.

If either the starting cell or the destination cell is blocked, or if there is no valid path between them, then the answer should be \(-1\). Otherwise, output the minimum number of steps required to reach the destination.

Note: The length of the path is defined as the number of cells visited along the path including the start and the destination. For example, a valid path that goes directly from the start to the destination in a 1-step move would have a length of 2.

inputFormat

The input is read from standard input (stdin) and is organized as follows:

• The first line contains an integer \(T\) denoting the number of test cases.
• For each test case:
• The first line contains an integer \(N\), the size of the grid.
• The following \(N\) lines each contain a string of length \(N\) consisting of characters . and #, representing the grid.

All input is provided via stdin.

outputFormat

For each test case, output a single line containing a single integer: the length of the shortest path from the top-left to the bottom-right cell. If no such path exists, output \(-1\). Output the answers to standard output (stdout), each on a new line.

## sample

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

7
-1
-1

</p>