Description

在一个3*3的九宫格棋盘里，放有8个数码，数码的数字分别是1~8等8个数字。可以通过在九宫格里平移数码来改变状态。数码在任何情况下都不能离开棋盘。给出8个数码的初始状态（没放数码的空格用0表示）和目标状态，问从初始状态到目标状态，最少需要经过多少次移动操作。

例如，初始状态为：

2 6 4
1 3 7
0 5 8

目标状态是：

8 1 5
7 3 6
4 0 2

最少的移动步数为31步。

Format

Input

第1行：9个空格分开的整数，表示初始状态

第2行：9个空格分开的整数，表示目标状态

整数都在0～8范围内，且不重复

Output

第1行：1个整数，表示从初始状态到目标状态的最少移动步数。如果无解，输出-1

Samples

2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2

31

Limitation

1s, 1024KiB for each test case.