1832 - 3×3Puzzle

問題

1から8までの整数が書かれた板と1マスの空間から成る3×3マスのパズルがあります。
1手を次のように定義します。
・空間と上下左右のいずれかに隣接する板を1つ選び、その板を空間へ移動させる。この時、もともと板があったマスが空間になる。
この操作を繰り返して、パズルを図のように並べるためにかかる手数の最小値を求めてください。 不可能な場合はそのことを報告してください。


$Q$個のパズルを解いてください。

入力

入力は以下の形式で標準入力から与えられる。

$Q$

1行目に整数$Q$が与えられる。

各パズルは以下の形式で標準入力から与えられる。

$A_{1,1}$ $A_{1,2}$ $A_{1,3}$
$A_{2,1}$ $A_{2,2}$ $A_{2,3}$
$A_{3,1}$ $A_{3,2}$ $A_{3,3}$

上から$i$行目、左から$j$行目に板があるのならば、その板に書かれている数が$A_{i,j}$に与えられる。
空間であるのならば、$A_{i,j}=0$である。

出力

$i$行目には、$i$個目のパズルを揃えるのにかかる手数の最小値を出力してください。ただし、不可能な場合は-1を出力してください。
出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq Q \leq 10^5$

入出力例

入力例1

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

出力例1

0
1
2

1つ目に関して、もとからパズルは完成しているので手数は0です。
2つ目に関して、6を上に移動すればよいので手数は1です。
3つ目に関して、7,8をこの順に左に移動すればよいので手数は2です。

入力例2

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

出力例2

28
-1
20
22
-1
17
18
25
-1
-1

パズルを完成させることが不可能なこともあります。