Minimum Trailing Zeros Path

Time limit1sMemory limit128 MB

Summary

Find a path from top-left to bottom-right of an N×N grid, avoiding zero cells, that minimizes trailing zeros in the product of visited cells.

Level: Medium6 of 10
Topics: Dynamic programming, Matrix, Math
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1
Input
```
3
5 7 6
4 0 1
3 2 5
```
Expected output
```
1
```
Example 2
Input
```
3
1 2 3
4 5 6
7 8 9
```
Expected output
```
0
```
Example 3
Input
```
4
1 3 0 0
0 8 2 25
6 5 0 3
0 15 7 4
```
Expected output
```
2
```