当前没有测试数据。

题目描述

翁老师来到了一个 $n\times m$ 的迷宫，每个位置有一个数值 $a_{i,j}$。

目前翁老师处在迷宫的左上角 $(1,1)$ 这个位置，他可以向右或向下走一步到下一个房间。

同时他可以进行若干次传送，每次传送可以花费 $1$ 的步数，直接传送至和当前房间数值 不互素 的任意一个房间。

现在他希望走到右下角，问最小步数是多少？

输入格式

第一行输入两个空格隔开的正整数 $n,m$

接下来 $n$ 行，每行 $m$ 个整数，代表 $a_{i,j}$

输出格式

输出一个整数代表移动步数

3 3
1 2 3
2 3 3
3 4 5

3

样例 1 解释

• 第一步，向右走一步，当前格子为 $2$。
• 第二步，传送到第三行第二列的 $4$。
• 第三步，向右走一步。

数据范围

对于 $30\%$ 的数据满足 $1\leq n,m\leq 10,1\leq a_{i,j}\leq 100$

对于 $100\%$ 的数据满足 $1\leq n,m\leq 500,1\leq a_{i,j}\leq 10^5$