Array Value

There is an N by N square grid. Each cell contains one non-negative integer.

You want to move from (1, 1) to (N, N). Each move must go either to the cell on the right or to the cell below the current cell, and you cannot leave the grid. You also cannot move onto a cell whose value is 0.

A path visits exactly 2N-1 cells, including the starting cell and the destination cell. The path value is the product of all numbers written in the cells visited by that path.

Among all valid paths, consider the smallest possible number of trailing zeros in the path value. This minimum is called the array value of the grid. Given the grid, compute its array value.

The input is guaranteed to contain at least one valid path from (1, 1) to (N, N).

The first line contains the grid size N. (2 <= N <= 1,000)

Each of the next N lines contains N integers separated by spaces. Each integer is between 0 and 1,000,000, inclusive.

Print the array value on the first line.