Sally Snail's Maximum Path

Sally Snail loves to wander on an \(N\times N\) chessboard (where \(1 < N \le 120\)). The board consists of open cells (represented by a dot: .) and obstacles (represented by a hash: #). Sally always starts from the top‐left corner (cell A1).

Sally moves only vertically (up or down) or horizontally (left or right). She may start by moving either right or down. Once she picks a direction, she continues moving in that direction until she is forced to stop. She stops when the next cell is either off the board, contains an obstacle, or has already been visited. At that point, she makes a 90° turn. At every turning point she has two choices: she can turn left (90° counter‐clockwise) or right (90° clockwise). If both directions are blocked, she stops her walk.

For example, consider the following board:

[ \boxed{\begin{array}{cccccccc} A & B & C & D & E & F & G & H\ S & . & . & . & . & . & # & .\ . & . & . & . & # & . & . & .\ . & . & . & . & . & . & . & .\ . & . & . & . & . & . & . & .\ . & . & . & . & . & # & . & .\ # & . & . & . & . & . & . & .\ . & . & . & . & . & . & . & .\ \end{array}}]

In this example, one possible route is illustrated below where Sally goes right, then down, right, down, left, up, and finally right. (Note that at some intersections alternative turning choices may yield a longer path.)

Your task is to determine the maximum number of cells Sally can visit if she chooses an optimal route.

inputFormat

The first line contains an integer \(N\) (the size of the board). Following this, there are \(N\) lines each with a string of length \(N\) consisting of the characters . and #. It is guaranteed that the top‐left cell (A1) is always open.

Example:

8
......#.
....#...
........
........
....#...
#.......
........
........

outputFormat

Output a single integer representing the maximum number of cells Sally can visit using an optimal route.

sample

3
...
...
...

8