T178595 八数码难题-加强版

九宫格拼图大家都很熟悉，在 3x3 的格子上摆放 8 块拼图，空出一个格子， 玩家要借助这 1 个空格上下左右滑动拼图，最终完成整幅图画。 本题中对拼图进行简化，将正确位置的拼图从左到右自上而下标记为 1-8， 空格定义为 0，像下面这样: 130 425 786 每次操作可以将 1 块拼图移向空格，像下面这样将 8 块拼图全部归位时完成游戏： 123 456 780 。 现在给定拼图的初始状态，希望求出完成拼图最少需要多少次移动。

输入文件第一行有一个数字 $N$，表示测试样例组数; 以下 $3*N$ 行共包含 $N$ 组测试数据，每组测试数据占 3 行，每行 3 个整数， 相邻数据用空格隔开。

输出文件包括 $N$ 行，对于每组测试数据，输出最少移动次数。

1 ≤ N ≤ 30，保证给定的拼图有解。