Minimum Trailing Zeros Path

A game board has N rows and N columns. Each square contains one non-negative integer.

At the start, a piece is on the upper-left square (1, 1). It must reach the lower-right square (N, N). In one move, the piece may move exactly one square down or exactly one square right. The piece cannot stand on a square whose value is 0.

The cost of a path is the product of all numbers on the squares in that path.

A path is optimal if the decimal representation of its cost has the smallest possible number of trailing zeros.

Compute the number of trailing zeros in the cost of an optimal path.

The first line contains the integer N (1 <= N <= 1000).

Each of the next N lines contains N integers describing the board. Every number is a non-negative integer not greater than 1,000,000.

For every test case, at least one valid path exists.

Print one integer: the minimum possible number of trailing zeros in the cost of a valid path.