Taco: Shortest Path in a Grid

You are given one or more grids, each of size (N \times N). Each cell in the grid is either walkable (denoted by a dot: '.') or blocked (denoted by a hash: '#'). The task is to find the length of the shortest path from the top-left cell ((0,0)) to the bottom-right cell ((N-1, N-1)) using only vertical and horizontal moves. You cannot move diagonally. If either the starting cell or the ending cell is blocked, or if there is no valid path, output (-1).

The input starts with an integer (T), representing the number of test cases. Each test case begins with an integer (N) followed by (N) lines, each representing a row of the grid.

Note: The distance is measured as the number of moves taken to arrive at the destination. For example, moving from one cell to an adjacent cell counts as one move.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (T), the number of test cases. For each test case, the first line is an integer (N) indicating the grid size, followed by (N) lines each containing (N) characters (either '.' or '#').

outputFormat

For each test case, output a single integer on its own line via standard output (stdout). This integer represents the length of the shortest path from the top-left cell to the bottom-right cell. If no such path exists, output (-1).## sample

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

4
-1