Taco Grid Shortest Path

You are given an N x N grid consisting of characters '.' (empty cell) and 'X' (obstacle). You need to determine the minimum number of steps required to move from the top-left cell to the bottom-right cell.

You can move one step at a time in any of the four directions: up, down, left, or right. Moving from one cell to an adjacent cell counts as one step. You cannot move diagonally and you cannot move into a cell with an obstacle.

If it is impossible to reach the destination, output \( -1 \).

The problem can be modeled using the following formula for a valid move from a cell \( (i,j) \) to \( (k,l) \):

[ \text{Valid if } |i-k| + |j-l| = 1 ]

Determine the fewest moves required to go from \( (0,0) \) to \( (N-1,N-1) \).

inputFormat

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

• The first line contains an integer \( T \) representing the number of test cases.
• For each test case, the first line contains an integer \( N \), the size of the grid.
• The next \( N \) lines each contain a string of length \( N \), where each character is either '.' or 'X'.

Note that there is no extra whitespace in the input.

outputFormat

For each test case, output a single line containing the minimum number of steps required to reach the bottom-right corner from the top-left corner. If the destination is unreachable, output -1.

The output should be printed to standard output (stdout), with each result on a new line.

## sample

1
3
...
.X.
...

4

</p>