在 3*3 的棋盘上有 8 个将牌,每一个将牌都刻有 1-8 数码中的某一个数码。棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。

给定一种初始时的将牌布局或结构(称作初始状态)和一个目标的布局(称作目标状态),问如何移动将牌,实现从初始状态到目标状态的改变,给出合法步骤中最小的移动步数。如下图所示

输入格式:首先输入一个数字 t (t>=1 && t<=10) 为测试数据的总数,接下来是 t 组测试数据, 每组测试数据均由 6 行,每行 3 个数字组成,前 3 行为初始状态,后 3 行为目标状态,空格由 0 表示,每组测试数据前面有一个空行。

输出格式:给出可以使初始状态转换到目标状态的最小移动次数,如果转化不到打印出-1。

输入样例:

2

2 8 3
1 6 4
7 0 5
2 3 0
1 8 4
7 6 5

2 8 3
1 6 4
7 0 5
2 8 3
1 4 6
7 0 5

输出样例:

3
-1