Description

小明有一个图的九宫格中，放着1~8 的数字卡片，还有一个格子空着。

与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

小明把最开始的图的局面记为：12345678.把结束图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
请找到最小的步骤，如果不能找到输出-1。

Format

Input

输入第一行包含九宫的初态，第二行包含九宫的终态。

Output

输出最少的步数，如果不存在方案，则输出-1。

Samples

12345678.
123.46758

3

13524678.
46758123.

22

Hint