고양이 랑이와 메리는 오목 게임의 변형인 냥목 게임을 하고 있다. 냥목 게임의 규칙은 복잡하니 점수 계산 방법만 보자.</p>

냥목 게임은 위 그림과 같은 $N \times N$ 크기의 바둑판에서 흑돌과 백돌을 이용해 진행된다.

랑이는 흑돌을, 메리는 백돌을 사용한다.

냥목 게임에서 랑이의 점수는 가로, 세로, 대각선 중 하나의 방향으로 연속하여 존재하는 가장 긴 흑돌의 길이가 된다.

잠시 집사가 돌아와서 메리가 반기러 간 사이 랑이는 메리의 돌 하나를 자신의 돌로 바꿔치기 하려고 한다. 즉, 랑이는 백돌 하나를 흑돌로 바꿀 수 있다.

랑이가 백돌 하나를 흑돌로 바꿀 때 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 자연수 $N$이 주어진다. ($2 \le N \le 1,000$)</p>

둘째 줄부터 $N$개 줄에는 줄마다 $N$개의 숫자가 공백으로 구분되어 주어진다. 이는 랑이가 돌을 바꿔치기하기 전 바둑판의 상태를 나타낸다. 각 수는 0, 1, 2 중 하나로 주어지고, 0은 비어 있는 위치를, 1은 흑돌을, 2는 백돌을 의미한다.

흑돌과 백돌은 각각 하나 이상 존재한다.

출력 형식

랑이가 얻을 수 있는 최대 점수를 출력한다.

예제 입력

5
1 1 0 1 0
1 1 0 0 0
1 0 2 1 0
1 0 2 1 0
0 1 0 0 1

예제 출력

5