小红的迷宫行走
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红来到了一个矩形迷宫，每个房间写着一个数字。小红初始在左上角的房间，她准备前往该迷宫的右下角房间，每次小红可以向右或者向下行走一步。
另外，小红可以进行若干次传送，每次可以花费1的步数，前往和当前房间不互素的任意一个房间。
现在，小红希望你求出从左上角走到右下角的最小步数。你能帮帮她吗？

输入描述:

第一行输入两个正整数n,m，代表迷宫的行数和列数。
接下来的n行，每行输入m个正整数a_{ij}，用来表示每个房间的数字。
1\leq n,m \leq 500
1\leq a_{ij} \leq 10^5

输出描述:

一个整数，代表左上角走到右下角的最小步数。
示例1

输入

复制 
3 3
1 2 3
2 3 3
3 4 5

输出

复制 
3

说明

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