究极汉诺塔

题目描述

汉诺塔大家都清楚的啦，普通的汉诺塔肯定难不倒大家啦，于是王木木出了一道究极汉诺塔的题，做完这题，你就可以大声说——

究极汉诺塔不知道比别的汉诺塔高到哪里去了，我和它谈笑风生

如图，给定初始局面和目标局面，求最少步数。

难题慎入

输入

多组测试数据

第一个数为数据组数n （1<=n<=60）

第二行包含n个1~3的整数，第i个数也就是初始局面中的第i个盘子所在的柱子编号（1号盘子最小，n号盘子最大）

第三行与第二行格式相同，为目标局面。

当n位0时，输入结束

输出

对于每组数据，输出一行，为最小步数的值

输入样例

4
1 1 1 1
1 2 2 1
3
1 1 1
2 2 2
3
1 2 3
3 2 1
4
1 1 1 1
1 1 1 1
0

输出样例

6
7
3
0

提示

普通的汉诺塔的步数是(1<<n)-1