有$3 \times 3$的方格，其中有八个数码。初始状态如下：

2 8 3
1 6 4
7 0 5

空格的上下左右四个方向都可以移动到空格中，称为一步。如$6$向下移变成：

2 8 3
1 0 4
7 6 5

给出目标状态，求最小要多少步可以从初始状态移到目标状态。

输入格式

6行，每行3个数字，如题意描述初始状态和结束状态

输出格式

一个数字，表示最小步数

样例

样例输入

2 8 3
1 6 4
7 0 5


1 2 3
8 0 4
7 6 5

样例输出

5

数据范围与提示

• 时间限制：$3000\mathrm{ms}$
• 空间限制：$512000\mathrm{KB}$