PLSQUARE - Palin Square

Kids just learnt about palindrome strings yesterday. Today, the teacher today was going to teach them about square shapes. But kids were still excited about palindrome strings. Therefore, the teacher came up with an idea combining square and palindrome in a game.

The teacher gave to kids a square board size of n, which is n row(s) * n column(s). Each row is a string of n character(s). Then, the teacher asked them to find the palindrome sub-square, which has maximum size. A palindrome sub-square is a sub square in board such that characters in each row of the sub square give out a palindrome string, and characters in each column of the sub square also give out a palindrome string.

Remember: A palindrome string is a string that has the property of reading the same in either direction, e.g. 'racecar', 'solos'.

When the teacher comes out from toilet, he was too happy and forgot the sub square in solution… Your task now is to help him to find out the maximum size of the palindrome sub square in the given board.

Input:

The first row contains an integer n, which is the size of the board. n<=200.

Each row in next n rows is a string contains only n lowercase characters, which describes the board.

Output:

Only 1 integer which is the maximum size of palindrome sub square in the board.

Example:

Input 1:
4
babb
acaz
babx
fdhk

Output 1:
3
Input 2:
1
a

Output 2:
1

Added by:Gầy :))
Date:2013-11-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:PRE-SCHOOL Team

hide comments
2015-06-07 19:32:59 Ankit Sultana
Really good problem. Though tags are a big spoiler.
2015-03-17 04:54:57 Naman Goyal
Really good problem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.