给你一个矩阵，只由小写或大写字母构成。求出它的最大对称子矩阵的边长。

其中对称矩阵是一个k*k的矩阵，它的元素关于从左下角到右上角的对角线对称。 
例如下面这个3* 3的矩阵是对称矩阵： 
cbx 
cpb 
zcc

Input

多组数据。每一组第一行是一个 n (0<n<=1000),下面是n行，每一行有n个字母，中间没有空格。数据以n=0结束。

Output

每组数据输出最大的对称矩阵的边长。

Sample Input

3
abx
cyb
zca
4
zaba
cbab
abbc
cacq
0

Sample Output

3
3

题目大意:中文题意

题目思路:每一个对称矩阵都可以由他的右上角元素得来,因为其关于左下-右上的对角线对称,所以我们可以把每一个元素当成左下角的元素,所以遍历当前元素时就可以去更新他左下角的元素.自己画图可以看出来状态转移方程

dp[i+1][j-1]+=当前点往上与当前点往右最大的相等长度

AC代码: