题目描述
通往藏宝库的通道打开了,走下一段长长的楼梯,钻过一条矮矮的地道,你和小可可终于来到了藏宝库的门前。随之而来的就是最后一个挑战,只要能打开宝库的门,里面的宝藏就是你们的了。
宝库的门依然是通过机关打开,这个门很奇怪,是一个正方形,被划分成许多大小一致的正方形的小方格,这些方格不是红色就是白色,猛看上去这些方格组成了许多红十字状的标志。根据藏宝图记载,只要找到门上最大的红十字,按下它中心的方格,宝库的门就能打开了。
红十字标志也是一个正方形,边长为(2k+1)*(2k+1),其中k为非负整数。它的四条边与门的边平行,而且恰由门上的(2k+1)*(2k+1)个小方格组成。这里,红十字标志是以白色为底色,红色为十字的颜色。假设用1表示红色,用0表示白色。对应到计算机处理的数据中,就是除了正中列与正中行全为1外,其余方格均为0。以下是几种不同大小的标志:
1*1:
1
3*3
010
111
010
5*5
00100
00100
11111
00100
00100
小可可被这个机关难到了,现在只有靠你了,请你帮助他在这个门上找到一个最大的红十字标志,输出它的边长即可。
输入格式
输入文件中第一行有一个整数n(1<=n<=2,000),表示门由n个方格组成。
以下n行,每行n个字符,每个字符都是0或1。数据中不会出现全为0的情况。
输出格式
输出一个数,即最大的红十字标志的边长。
样例输入
样例输出