# Anton's Vyshyvanka

Anton has a large collection of various vyshyvankas (traditional embroidered shirts), each possessing different magical powers.

The power of a vyshyvanka is determined by its pattern and is defined by the largest rune that can be identified in it. The pattern is a square matrix of size $n$, consisting of blue and yellow cells. A rune of size $k$ can be represented as $4$ identical chessboards of size $2k−1$ (with blue top left cell) arranged in the shape of a "+"-cross (formed by one vertical and one horizontal lines) with a hole in the middle. We consider that there is a rune of size $k$ in the pattern if and only if we can place our rune on the field such that the blue cells in the rune match the blue cells in the pattern. Note that it is not necessary for the yellow cells in the rune to match; they can coincide with either blue or yellow cells in the pattern.

Here is an example of a rune of size $2$ (four patterns of this rune are marked using green squares around them):

Note that any group of yellow cells in this pattern may also be blue and the rune will still exist:

Also, please note that this is not a rune of size $1$, since patterns should be arranged in a form of "+"-cross:

Anton urgently needs to know the power of the vyshyvanka before wearing it, but unfortunately, at that time he was very busy, so he asked Chmyaaax (not yet evil) to write a program that would determine the power of the vyshyvanka based on the pattern. However, Chmyaks tricked him and, stealing something important, ran away. Therefore, now Anton is asking you to do it.

## Input

The first line contains one integer $n$ $(1≤n≤4,000)$ — the size of the given pattern.

Each of the next $n$ lines contains $n$ characters, each of which is either '`.`

', or '`#`

', where '`.`

' represents a yellow cell and '`#`

' — a blue cell.

## Output

In the only line, you need to output the power of the given pattern.

Please note that, if and only if there are no runes on the pattern, the answer is $0$.

## Examples

## Note

The maximum rune on the pattern from the first example has a size of one:

The rune on the pattern of the second example is shown on the pictures in the statement. It can be shown that there is no rune of size $3$ on it.

Here is the vyshyvanka from the third sample:

Here is the only rune of size $1$ that can be found on it:

It can be shown that there are no runes of size $2$ or more here.

In the fourth sample, it can be shown that there are no runes at all. Again, please, note that the answer can be $0$.

## Scoring

($24$ points): it is guaranteed that the answer is at most $2$;

($26$ points): $n≤70$;

($37$ points): $n≤300$;

($31$ points): $n≤1,000$;

($52$ points): $n≤2,500$;

($80$ points): no additional constraints.