测试数据来自 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\)，则代表该位置暂无滑块。