정수로 이루어진 \(N \times N\) 크기의 격자가 있다.

격자의 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸까지 최단 경로로 이동하려고 한다. 한 칸에서 다른 칸으로 이동할 때는 변을 공유하는 인접한 칸으로만 이동할 수 있다.

이동하면서 방문한 칸의 정수를 순서대로 모으면 하나의 수열을 만들 수 있다. 수열에서 일부 원소를 골라 원래 순서를 유지한 채 나열했을 때, 모든 원소가 바로 앞의 원소보다 큰 수열을 증가하는 부분 수열이라고 한다. 증가하는 부분 수열 중 길이가 가장 긴 것을 가장 긴 증가하는 부분 수열이라고 한다.

선택한 최단 경로에 따라 서로 다른 수열이 만들어질 수 있다. 가능한 모든 최단 경로로 만든 수열 중, 가장 긴 증가하는 부분 수열의 길이가 최대가 되는 경우를 구하여라.

입력

첫째 줄에 격자의 크기 \(N\)이 주어진다.

다음 \(N\)개의 줄에 각각 \(N\)개의 정수가 공백으로 구분되어 주어진다.

• \(1 \le N \le 100\)
• 각 칸에 적힌 정수는 \(1\) 이상 \(10,000\) 이하이다.

출력

첫째 줄에 가능한 수열들의 가장 긴 증가하는 부분 수열 길이 중 최댓값을 출력한다.

예제 입력 1

4
5 1 2 3
6 7 1 4
1 8 9 5
2 3 10 6

예제 출력 1

6

예제 설명 1

맨 윗줄을 따라 오른쪽으로 이동한 뒤 아래로 이동하면 다음 수열을 만들 수 있다.

\(5, 1, 2, 3, 4, 5, 6\)

이 수열에서 \(1, 2, 3, 4, 5, 6\)을 고르면 길이가 \(6\)인 증가하는 부분 수열을 만들 수 있다. 출발점에서 만난 첫 번째 5는 부분 수열에 포함하지 않아도 된다.

예제 입력 2

3
9 8 7
8 7 6
7 6 5

예제 출력 2

1

예제 설명 2

어떤 최단 경로를 선택해도 방문하는 수가 계속 감소한다. 따라서 증가하는 부분 수열에는 하나의 원소만 포함할 수 있다.