We have a two-dimensional $N×N$ array.
Each element of the array is either $0$ or $1$.
Write a program to compute the length of the longest consecutive “$1$”'s in a row, in a column, or in a diagonal direction.
You only need to consider the diagonal direction as going from $(x, y)$ to $(x+1, y+1)$, as in the following figure.

sample

The following figure has three examples.

sample

Input Format

The first line has the integer $N$, the size of the array.
The next $N$ lines have $N$ integers, which are either $1$ or $0$.
They are the elements of the array.

$0 \lt N \lt 1000$

Output Format

The output has only one integer -- the length of the longest consecutive $1$'s in a row, in a column, or in the diagonal direction.

Subtask

50 points: Compute the length of the longest continuous $1$'s in a row or in a column. You can safely ignore the diagonal direction.

50 points: Compute the length of the longest continuous $1$'s in a row, in a column, or in the diagonal direction.

Sample Input 1

5

1 0 1 1 0

1 0 0 0 1

0 1 1 1 1

0 1 0 0 1

0 0 0 1 0

Sample Output 1

4

Sample Input 2

5

1 0 1 1 0

1 0 0 0 1

1 0 1 1 0

0 1 0 0 1

0 0 0 0 1

Sample Output 2

3

Sample Input 3

5

0 0 1 1 0

0 0 0 0 1

1 1 0 1 0

0 1 1 0 1

0 0 0 1 1

Sample Output 3

3

Hint

You need to get the answer by exmaining the data only once. That is, if you are looking for the answer in a row, you need to scan the row once and get the answer. You cannot try every element as a possible starting point of the longest sequence of 1's, because you will get TLE.