题目描述

在 n*n 的数字矩阵中，从左下角开始，每次只能向上或向右进入相邻的方格，不能走到方格外，一直走到右上角，问路径上数的乘积中结尾最多有多少 0 ？

输入格式

第 1 行一个数 n，范围 [1,100]；

第 2 到 n+1 行，每行 n 个整数，范围 [1,1000]

输出格式

一个整数。

样例

5
1 2 3 4 5
4 5 6 5 125
25 3 8 12 21
1 10 2 51 3
4 1 27 32 8

7

样例解释

乘积尾部最多0的的路径序列是 4 1 25 3 8 12 5 125 5