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

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

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

1 
1 3 0
4 2 5
7 8 6

4