测试数据来自 Scoj/1001

Description

$Scarral$到达了密室大门，发现大门左侧有一行文字。

想打开大门，请先完成右侧的拼图！拼图中隐含着密码。

$Scarral$往右一看，果然有个数字拼图。

$Scarral$转念一想：

这不就是数字华容道吗？！！

拼图是一个 $n\times n$ 的由木块组成的矩阵，木块编号为 $1$~$n^2-1$ 每个木块都只能相邻的空格移动，不能拿起。

经过若干次的移动，可以将拼移动为 $1$~$n^2-1$ 的顺序矩阵。

如 $n=3$ 时，最后要求移动为

1 2 3
4 5 6
7 8 空


给出华容道的大小 $n$ 和当前华容道的乱序摆放位置，求还原原序的最小步数。

---

Input

第 $1$ 行 $1$ 个正整数 $n$，表示有一个 $n \times n$ 的华容道。
接下来键入 $n$ 行 $n$ 列的矩阵，表示当前华容道的乱序摆放位置，若某数为 $0$，则代表该位置暂无滑块。