Longest Spiral Path in a Park

The park is represented as an \(N \times N\) grid. The cell in the \(i\)-th row and \(j\)-th column is denoted by \((i, j)\). Each cell is either a walkable road or an unwalkable fountain.

You want to ride along a spiral path. A spiral path is defined as follows:

• Start from any cell, choose an initial direction and move at least \(1\) cell;
• Then, make a right turn (90° clockwise) and move at least \(1\) cell;
• Again, make another right turn and move at least \(1\) cell;
• Finally, make a third right turn and move at least \(1\) cell.

During the spiral path, you cannot go onto a fountain cell. The length of the path is the total number of cells visited including both the starting and the ending cell.

Your task is to find the longest spiral path that you can ride. It is guaranteed that there is at least one valid spiral path.

The directions are considered in the order: right, down, left, up (and then repeating). The right turn means turning 90° clockwise. All formulas are given in \(\LaTeX\) format.

inputFormat

The first line of input contains a single integer \(N\) representing the dimensions of the grid. \(N\) is followed by \(N\) lines, each containing a string of length \(N\). Each character in the string is either a '.' (representing a walkable road) or a '#' (representing a fountain).

For example:

3
...
.#.
...

outputFormat

Output a single integer representing the maximum number of cells that can be included in a spiral path.

sample

3
...
.#.
...

7