Taco: Minimum Steps in a Grid

You are given a square grid of size \(N\) which consists of characters '.' and '#' where '.' represents an open cell and '#' represents an obstacle. Your task is to find the minimum number of steps required to move from the top-left corner (cell (0,0)) to the bottom-right corner (cell (N-1, N-1)) by moving up, down, left, or right.

If either the starting cell or the ending cell is blocked, or if there is no valid path, output -1.

Note: The grid cells are indexed from 0. The number of steps is defined as the number of moves between cells along the valid path.

The underlying idea is to perform a Breadth-First Search (BFS) starting from the top-left corner to efficiently compute the shortest path. The movement directions can be represented by the set \(\{(1,0), (-1,0), (0,1), (0,-1)\}\).

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N
row1
row2
... (N rows)
N
row1
row2
... (N rows)
... (repeated T times)

Where:

• T is the number of test cases.
• For each test case, the first line contains an integer N denoting the size of the grid.
• The following N lines each contain a string of length N that represents the grid row, consisting only of characters '.' and '#'.

outputFormat

For each test case, output a single line containing the minimum number of steps required to reach from the top-left corner to the bottom-right corner. If such a path does not exist, output -1.

## sample

1
3
..#
.#.
...

4