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

游戏的规则如下：

• 拼图由 3 \times 3 的格子组成，其中包含数字 1 到 8 的卡片和一个空格。

• 只有与空格相邻的卡片可以移动到空格中。

• 游戏会给出拼图的初始图形和通过移动卡片得到的目标图形。

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

比如，下面给出了拼图的初始图形和目标图形。

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

因此上图中的初始图形为：12345#678，目标图形为：1#2453678。

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

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

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

样例 1 说明

样例 1 的示意图，请参考题目描述。

可以发现，只需要移动 2 步，就可以从初始图形移动到目标图形。

数据范围

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

月赛广搜2024