题目描述

Gakkipan在玩一个电子游戏，他操控的人物带伤进入了一个满是陷阱的迷宫，迷宫中是一个大小为n*n的平面网格区域，入口在左上角，出口在右下角，迷宫中每个格子都可能存在着一个陷阱，每个陷阱有一个威力值a，如果踏过存在该陷阱的格子后，Gakkipan人物的伤势变为之前的a倍，若没有陷阱的格子该值表示为1，一开始Gakkipan的伤势值为1，Gakkipan的人物只能朝右或者朝下走，在到达出口后，Gakkipan有一门独门心法，可以且必须把伤势的值转化为最终伤势末尾后缀0的个数，求走出迷宫的最小伤势。

文件输入

输入第一行两个正整数n，表示迷宫的大小
接下来n行，每行n个正整数，表示迷宫中每个格子的陷阱威力值

文件输出

输出最终转化后的伤势值

输入样例

3
1 2 3
4 5 6
7 8 9

输出样例

0

数据规模

对于前30%的数据，n<=10
对于100%的数据，n<=1000,所有陷阱的威力值a<=10^9