十的倍数

小码哥在太平洋一个偏僻的小岛上走入了一个 $N \times N$ 的数字迷宫,迷宫的每个格子中都有一个非负整数，他现在位于最左上角的格子 $(1,1)$，他需要走到最右下的出口 $(N,N)$ 才能够解救。现在小码哥从 $(1,1)$ 起点出发，每次只能往下走一格或者往右走一格，最终到达位于 $(N,N)$ 的出口。

现在不仅要求小码哥能够到达终点，同时也要求一路上所经过格子的数字乘积的末尾的 0 的个数最少。同时迷宫中可能存在数字为 0 的格子，要求路径中不能经过数值是 0 的点。

输入格式

• 第一行一个整数 $N$，表示输入一个 $N \times N$ 的矩阵。
• 接下来 $N$ 行，每行 $N$ 个整数，来描述这个矩阵。
• 矩阵中的所有元素都是非负整数。

输出格式

一个数 $ans$，表示最少的 0 的尾数个数，保证肯定有解。

样例输入

4
1 3 0 0
0 8 2 25
6 5 0 3
0 15 7 4

样例输出

2

数据范围

• 对于30% 的数据，满足 $1 \le N \le 100$；
• 对于60% 的数据，满足 $1 \le N \le 500$；
• 对于100% 的数据，满足 $1 \le N \le 1000$，矩阵中的元素 $\le 10^9$。