Maximal Regular Football Pitch

In the city of Debrecen there is a square forest called Nagyerdő that can be represented as an \(N \times N\) grid. The rows are numbered from \(0\) to \(N-1\) from north to south and the columns from \(0\) to \(N-1\) from west to east. The cell in row \(r\) and column \(c\) is denoted as \((r, c)\).

Each cell in the forest is either empty or contains a tree, and there is at least one empty cell.

DVSC, the most renowned sports club of the city, is planning to construct a new football pitch within the forest. A football pitch of size \(s\) (with \(s \ge 1\)) is defined as a set of \(s\) distinct empty cells \((r_0, c_0), \ldots, (r_{s-1}, c_{s-1})\) that satisfy the following:

• Each cell \((r_i, c_i)\) is empty for \(0 \le i \le s-1\);
• For every two distinct indices \(i\) and \(j\) (with \(0 \le i < j \le s-1\)), at least one of \(r_i \neq r_j\) or \(c_i \neq c_j\) holds.

The game is played by passing the ball between cells of the pitch. A direct pass is defined as one of the following two moves:

• Horizontal pass: If the pitch contains every cell between \((r, a)\) and \((r, b)\) in row \(r\) (that is, for all \(k\) between \(\min(a,b)\) and \(\max(a,b)\), the cell \((r,k)\) is in the pitch), then the ball can be passed directly from \((r, a)\) to \((r, b)\), where \(0 \le r,a,b < N\) and \(a \neq b\).

• Vertical pass: If the pitch contains every cell between \((a, c)\) and \((b, c)\) in column \(c\) (that is, for all \(k\) between \(\min(a,b)\) and \(\max(a,b)\), the cell \((k,c)\) is in the pitch), then the ball can be passed directly from \((a, c)\) to \((b, c)\), where \(0 \le c,a,b < N\) and \(a \neq b\).

A pitch is said to be regular if for any two cells in the pitch the ball can be passed from one to the other using at most 2 direct passes. (Note that any pitch of size \(1\) is trivially regular.)

For example, consider a forest with \(N = 5\) where a tree is placed in cell \((1,0)\) and cell \((4,2)\) while all other cells are empty. Although several pitches can be constructed, some are regular and some are not; see the figure in the problem statement.

Your task is to find the largest \(s\) such that there exists a regular football pitch of size \(s\) within the forest.

inputFormat

The first line contains an integer \(N\) representing the size of the forest grid. The following \(N\) lines each contain a string of length \(N\). Each character is either a '.' (denoting an empty cell) or a '#' (denoting a tree). It is guaranteed that there is at least one empty cell.

outputFormat

Output a single integer which is the maximum \(s\) (number of cells) such that a regular football pitch of size \(s\) can be constructed in the forest.

sample

5
.....
#....
.....
.....
..#..

10