예술을 사랑하는 사람들이 시장에 모여서 그들의 그림을 서로 거래하려고 한다. 모든 그림의 거래는 다음과 같은 조건을 만족해야 한다.</p>

1. 그림을 팔 때, 그림을 산 가격보다 크거나 같은 가격으로 팔아야 한다.
2. 같은 그림을 두 번 이상 사는 것은 불가능하다.

방금 시장에 새로운 그림이 들어왔다. 1번 아티스트는 그 그림을 외부 상인에게 가격 0을 주고 샀다. 이제 그 그림을 자신의 예술가 친구들에게 팔려고 한다. 위의 조건을 모두 만족하는 거래만 이루어진다고 가정했을 때, 그림을 소유했던 사람의 수의 최댓값을 출력하는 프로그램을 작성하시오. (1번 아티스트와 마지막으로 그 그림을 소유한 사람도 포함한다).

입력 형식

첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다.</p>

둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에게 그 그림을 살 때의 가격이다. 모든 가격은 0이 제일 낮은 가격이고, 9가 제일 높은 가격이다.

출력 형식

첫째 줄에 그 그림을 소유 했던 사람들 (잠시라도 소유했던 사람도 포함)의 최댓값을 출력한다.

예제 입력 1

3
022
101
110

예제 출력 1

2

예제 입력 2

2
01
10

예제 출력 2

2

예제 입력 3

5
01231
00231
00031
00002
00000

예제 출력 3

4

예제 입력 4

5
15555
11111
15111
11111
11111

예제 출력 4

3

예제 입력 5

10
0100000000
0020000000
0003000000
0000400000
0000050000
0000006000
0000000700
0000000080
0000000009
1111111111

예제 출력 5

10