# 50120. Consecutive 1's

## I'm a slow walker, but I never walk backwards.

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.

• 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

51 0 1 1 01 0 0 0 10 1 1 1 10 1 0 0 10 0 0 1 0


## Sample Output 1

4


## Sample Input 2

51 0 1 1 01 0 0 0 11 0 1 1 00 1 0 0 10 0 0 0 1


## Sample Output 2

3


## Sample Input 3

50 0 1 1 00 0 0 0 11 1 0 1 00 1 1 0 10 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.