/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
グリッド(マス目)上に書かれた以下のような図形を C と呼びます。
### #### #####
#.. #... #....
### #... #....
#### #....
#####
上図にあるのは、左からレベル 1,2,3 の C です。
厳密には、正整数 l に対し、レベル l の C を以下のように定義します。
- レベル l の C は、 (l+2) \times (l+2) の正方形状のグリッドである。
- 正方形のうち、上・左・下の境界に接するマスには
#が書かれている。 - それ以外のマスには
.が書かれている。
N \times N のグリッドが与えられ、各マスには # か . が書かれています。
グリッドは N 個の文字列 S_1,S_2,\dots,S_N として与えられ、 S_i の j 文字目が上から i 行目、左から j 列目のマスに書かれた文字を表します。
このグリッドから (連結な) 正方形を抜き出して得られる最もレベルの高い C のレベルを答えてください。
但し、グリッドからどのような正方形を抜き出してもそれが C とならない場合、 0 と答えてください。
制約
- N は 3 以上 300 以下の整数
- S_i は長さ N の
#と.からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
4 #### .#.. .### #..#
出力例 1
1
グリッドのうち上から 1 行目から 3 行目、左から 2 列目から 4 列目の正方形を抜き出すと、これはレベル 1 の C です。
このグリッドから、レベル 2 以上の C を抜き出すことはできません。
入力例 2
5 .#### .###. ####. ##..# ###.#
出力例 2
0
このグリッドから C を抜き出すことはできません。
入力例 3
10 .###...### .#.....#.. .######### ...#...... ...#...... ...#...... ########## #.....#... #.....#... ####..####
出力例 3
3
Problem Statement
An object on a grid like these is called a C.
### #### #####
#.. #... #....
### #... #....
#### #....
#####
Illustrated above are Cs of level 1, 2, and 3, from left to right.
Formally, for a positive integer l, a C* of level l is defined as follows.
- A C of level l is an (l+2) \times (l+2) square grid.
- Every cell on the upper, left, or lower border of the square has
#written on it. - Every other cell has
.written on it.
You are given an N \times N grid. Each cell has # or . written on it.
The grid is described by N strings S_1,S_2,\dots,S_N; the j-th character of S_i represents the character written on the cell in the i-th row from the top and j-th column from the left.
Find the maximum level of a C that can be obtained by extracting a (connected) square from this grid.
If no square extracted from the grid forms a C, print 0.
Constraints
- N is an integer between 3 and 300, inclusive.
- S_i is a length-N string consisting of
#and..
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer as an integer.
Sample Input 1
4 #### .#.. .### #..#
Sample Output 1
1
If you extract the square consisting of 1-st through 3-rd rows from the top and 2-nd through 4-th columns, it forms a C of level 1.
One cannot extract a C of level 2 or greater from this grid.
Sample Input 2
5 .#### .###. ####. ##..# ###.#
Sample Output 2
0
One cannot extract a C from this grid.
Sample Input 3
10 .###...### .#.....#.. .######### ...#...... ...#...... ...#...... ########## #.....#... #.....#... ####..####
Sample Output 3
3