Ball Again

Time Limit: 1 Second    Memory Limit: 32768 KB

After the ball held on October, 2004 (on that time, we are enjoying our last ZOJ Monthly Contest), all the attendants have had more friends. Thanks for your help on arranging them on the ball last time. But now a new problem comes, and puzzled me a lot. I have to come to ask for your help again.

The new friends are all busy in attending meetings. If there are M (M >= 3) persons sitting in a circle and everyone is a friend of his adjacent person, then a meeting will be held for these M people. Therefore, there will be a lot of meetings among them, which makes me busy in preparing the dining table for them.

The dining tables all have fixed size and each can accommodate K seats. I wanted to use these tables without any space left during each meeting. For example, if 6 persons have a meeting at a time, the type of table with parameter K = 1, 2, 3, 6 will meet our requirement and K = 4 will not bacause it will leave 2 seats vacant as you have to use two tables for the meeting.

Now I want to know, what's the maximum value of K.

Input

There are several test cases. Each case starts with a positive integer N (3 < N <= 100), denotes the number of persons coming back from the ball. Then N lines follows. Each line contains N integers either '1' or '0', with exactly one space between adjacent. A '1' in the ith row and jth column represents that a[j] is a friend of a[i] and a '0' means not.

Proceed the cases until N = 0, which should not be proceeded.

Output

One positive integer K on a single line for each case, which means the maximum size of dining table.

Sample Input

4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
6
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0

Sample Output

1
2

Submit

Source: ZOJ Monthly, November 2004