Migrated from Lutece 1380 Xiper的奇妙历险(3)

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

打败了日天，$Xiper$好不容易从火中逃了出来。在豪宅外守候的潘警官发现了身受重伤的$Xiper$，连忙把$Xiper$送进了医院。

$Xiper$躺了三天三夜，才从医院醒来。一抬头，$Xiper$赫然发现，照顾他的护士正是十年未见的卿学姐！

两人又坠入了爱河之中，并经历了一番不可描述的生命的大和谐。

（潘警官：）

出院后，潘警官告诉$Xiper$，日天并没有死，还笼络了一批手下，逃到了咸鱼镇。

与其同时，岳老师出现在了$Xiper$面前。他告诉$Xiper$，只有学会古老的膜法，才能打败日天，拯救世界。

于是$Xiper$开始了膜法的修行。为了锻炼$Xiper$的定力，每天岳老师都会把$Xiper$放在在一个九宫格之中，在其它的格子上都放着形状各异的光剑。每次$Xiper$可以拔出四周的一把光剑，与这把光剑交换位置。

最终，$Xiper$要处于第$3$行第$3$列的位置，且在其它位置上，第$i$行第$j$列的光剑编号为$(i - 1) * 3 + j$。

智商高达666的$Xiper$当然知道他要到达目标的最少次数是多少，你知道吗？

Input

第一行一个数字$T$($1<=1<=10000$)，代表训练的天数。

对于每天，都有一个$3*3$行的矩阵，描述九宫格的状态，$x$代表xiper。

Output

对于每组数据，输出最少的步数$step$。如果无解则输出$-1$。

Samples

1
1 2 x
4 5 3
7 8 6

2

Note

在下周日天，听说你会暴搜？

Resources

2016 UESTC Training for Search Algorithm & String