배열값

가로와 세로가 각각 N칸인 정사각형 배열이 있다. 각 칸에는 음이 아닌 정수가 하나 적혀 있다.

(1, 1)에서 (N, N)까지 이동하려고 한다. 한 번 이동할 때는 현재 칸의 오른쪽 칸 또는 아래쪽 칸으로만 갈 수 있으며, 배열 밖으로 나갈 수 없다. 값이 0인 칸으로는 이동할 수 없다.

하나의 경로는 시작 칸과 도착 칸을 포함해 모두 2N-1개의 칸을 지난다. 그 경로에서 지나간 칸들에 적힌 수를 모두 곱한 값을 그 경로의 경로값이라고 한다.

가능한 모든 경로 중에서 경로값의 끝자리 0의 개수가 가장 적을 때, 그 최소 개수를 이 배열의 배열값이라고 한다. 배열이 주어졌을 때 배열값을 구하라.

입력은 항상 (1, 1)에서 (N, N)까지 이동할 수 있는 경우만 주어진다.

첫째 줄에 배열의 크기 N이 주어진다. (2 <= N <= 1,000)

다음 N개의 줄에는 배열에 적힌 정수 N개가 공백으로 구분되어 주어진다. 각 정수는 0 이상 1,000,000 이하이다.

첫째 줄에 배열값을 출력한다.