광산 경로

NxN 크기의 광산이 있다. 광부는 좌상단 (1,1)에서 출발하여 우하단 (N,N)까지 이동한다. 이동은 오른쪽 또는 아래쪽으로만 가능하다.

각 칸에는 광물의 가치가 적혀 있다. 광부가 이동 경로에서 모은 광물 가치의 곱을 구할 때, 곱의 끝자리 0의 개수를 최소화하는 프로그램을 작성하시오.

값이 0인 칸은 통과할 수 없다. 모든 칸의 값은 0 이상 1,000,000 이하이다.

곱이 0인 경우(0인 칸을 피할 수 없는 경로) 끝자리 0의 개수는 0으로 센다.

입력

첫째 줄에 N이 주어진다. (1 <= N <= 1,000)

둘째 줄부터 N개의 줄에 각각 N개의 정수가 공백으로 구분되어 주어진다.

출력

최소 끝자리 0의 개수를 출력한다. 경로가 존재하지 않으면 -1을 출력한다.

입출력 예시

입력 1

3
1 2 3
4 0 5
6 7 8

출력 1

0

입력 2

3
10 10 10
10 10 10
10 10 10

출력 2

5