题目描述

给定一个 \(N×M\) 的矩阵，记录左上角为\((1,1)\)，右下角为\((N,M)\)。现在从\((1,1)\)开始取数，每次只能向下或向右移动一个单位，最终到达\((N,M)\)，我们把路径上所有的数相乘，记为\(C\)。使 \(C\) 的结果最大已经不能满足我们了，现在我们想让 \(C\) 末尾的零最 少。

注意：\(11000\) 末尾有 \(3\) 个零， \(100000100\) 末尾有 \(2\) 个零。

格式

输入格式

第一行包含两个正整数 \(N,M\) 表示矩阵大小。

接下来 \(N\) 行每行 \(M\) 个正整数给出整个矩阵。

输出格式

包含一个整数表示所求 最小值。

样例1

样例输入1

3 3
1 2 3
10 5 100
10 8 9

样例输出1

1

限制

\(30\%\)的数据：\(N,M≤5\)；

\(100\%\)的数据：\(1 \lt N,M≤1000\)，所有输入的数据不超过\(2^{31}-1\)。