SP4546 ANARC08A - Tobo or not Tobo

Tobo游戏在一个从 $1$ 到 $9$ 编号的九宫格当中进行，九宫格当中还有四个从 $A$ 到 $D$ 编号的圆盘，如图(a)所示。每一个圆盘都可以向任意方向旋转90度任意次，每次旋转某个圆盘时，会使得它所连接的四个方格同样与它一起旋转，如图(b)(c)所示。 每一次游玩时，都会把局面打乱，游戏的目标就是在有限步之内复原所有的方格回到图(a)所示的状态（圆盘的方向无所谓）。请编写一个程序，算出最少需要多少步可以复原。

输入包含多组数据。 每组数据包含一行一个长度为10的数字串。 其中第一位表示操作次数的上限，后9位从左至右、从上至下描述了九宫格的初始状态（样例第一行就是图(c)所示的局面）。 输入以一行全0的字符串结束。

注意输出第一组数据前需要输出一次换行,见样例输出（注：样例中的 `\n` 指的是换行而不是输出这个字符串本身）。 Translated by Hanoist