当前没有测试数据。

题目描述

小 $A$ 同学在一个古老的图书馆中，发现了一个经典的拼图游戏。

游戏的规则如下：

• 拼图由 $3 \times 3$ 的格子组成，其中包含数字 $1$ 到 $8$ 的卡片和一个空格。
• 只有 与空格相邻 的卡片可以移动到空格中。
• 游戏会给出拼图的初始图形和通过移动卡片得到的目标图形。

请你编程计算出，从拼图初始图形到移动卡片得到目标图形，最少需要移动的步数。如果无论如何都无法得到目标图形，则输出字母 "N"。

为了方便输入，我们将拼图上每个位置的状态，按从上到下，从左到右的顺序记录下来，其中空格用 # 代替。

输入格式

第 $1$ 行输入一个字符串，长度为 $9$，表示拼图的初始图形。

第 $2$ 行输入一个字符串，长度为 $9$，表示拼图的目标图形。

输出格式

输出一个整数，代表最少需要移动步数。如果无论如何都无法得到目标图形，则输出字母 N。

样例

输入

12345#678
1#2453678

输出

2

数据范围

输入数据保证 $2$ 个字符串均包含 $1 \sim 8$ 之间的整数和一个字符 #。