Shortest Path in a Grid

You are given a square grid of size \(n \times n\) where each cell is either free (denoted by '.') or blocked (denoted by 'X'). Your task is to find the length of the shortest path from the top-left cell to the bottom-right cell. You can move only in the four cardinal directions (up, down, left, right) and you cannot pass through obstacles.

If either the start or the destination cell is blocked, or if there is no valid path, output \(-1\).

The input consists of multiple datasets. Each dataset starts with an integer \(n\) (\(n > 0\)) denoting the size of the grid, followed by \(n\) lines each containing \(n\) characters. A dataset with \(n = 0\) indicates the termination of input and should not be processed.

Example:

5
.....
.X.X.
...X.
.X.X.
.....
5
XXX..
X..XX
.X..X
X...X
.....
0

The output for the above example should be:

8
-1

inputFormat

The standard input will contain multiple datasets. Each dataset begins with an integer \(n\) (where \(n > 0\)), followed by \(n\) lines representing a grid. The grid is made up of the characters '.' (representing a free cell) and 'X' (representing an obstacle). Input terminates with a line containing a single 0, which should not be processed.

Note: All input should be read from standard input (stdin).

outputFormat

For each dataset, print a single integer: the length of the shortest path from the top-left cell (1,1) to the bottom-right cell (n,n). If no path exists, print \(-1\). Each output should be printed on a new line.

Note: All output should be written to standard output (stdout).

## sample

5
.....
.X.X.
...X.
.X.X.
.....
5
XXX..
X..XX
.X..X
X...X
.....
0

8
-1

</p>