Battlefield Pathfinding

You are given one or more square grids representing a battlefield. Each grid is composed of . and # characters, where . represents an open cell and # represents a wall.

Your task is to determine the minimum number of cells needed to traverse from any open cell in the top row to any open cell in the bottom row. You can move horizontally or vertically (but not diagonally) and you may only step on open cells. The starting cell is counted as part of the path. If it is impossible to reach the bottom row, output -1.

Note: Although the function is named longest_path, you are actually required to compute the shortest valid path (in terms of number of cells traversed, including the starting cell).

The grids are always square, and each grid is given by its size m followed by m lines of exactly m characters.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains a single integer t representing the number of grids.
• For each grid, the first line contains an integer m representing the size of the grid (the grid is m x m).
• This is followed by m lines, each containing a string of length m consisting of . and #.

outputFormat

For each grid, output a single line to standard output (stdout) containing a single integer: the minimum number of cells in a valid path from the top to the bottom row, or -1 if no such path exists.

## sample

3
5
.#...
.....
##..#
.....
.#.#.
4
....
.#..
.#..
....
3
###
###
###

5
4
-1

</p>