끝자리 0이 최소인 경로

N행 N열로 이루어진 게임판이 있다. 각 칸에는 음이 아닌 정수 하나가 적혀 있다.

처음에 말은 왼쪽 위 칸 (1, 1)에 놓여 있다. 말은 오른쪽 아래 칸 (N, N)까지 이동해야 한다. 한 번 움직일 때마다 정확히 한 칸 아래로 가거나 정확히 한 칸 오른쪽으로 갈 수 있다. 값이 0인 칸에는 말을 놓을 수 없다.

어떤 경로의 비용은 그 경로에 포함된 모든 칸의 수를 곱한 값이다.

경로의 비용을 십진수로 썼을 때 끝에 붙는 0의 개수가 가능한 한 적은 경로를 최적 경로라고 한다.

최적 경로의 비용 끝에 붙는 0의 개수를 구하라.

첫째 줄에 정수 N이 주어진다 (1 <= N <= 1000).

다음 N개 줄에는 게임판을 나타내는 정수 N개가 주어진다. 모든 수는 1,000,000 이하의 음이 아닌 정수이다.

모든 테스트 데이터에는 항상 가능한 경로가 하나 이상 존재한다.

가능한 경로의 비용 끝에 붙는 0의 개수의 최솟값을 정수 하나로 출력한다.