1017 - 拼图

拼图游戏由一个3×3的棋盘和数字1-9组成。目标是达到以下最终状态: 1 2 3 4 5 6 7 8 9 每次如果相邻两个数字之和为质数,则可以进行交换。 相邻:上下左右四联通 给定一个棋盘初始状态,求到达最终状态的最短步数。

输入

第一行为正整数T,表示存在T组测试数据,1≤T≤50。 对于每组测试数据,输入3行,每行3个数字表示棋盘。 输入保证合法,棋盘中的9个数字仅为1-9。

输出

对于每组测试数据输出一个整数表示答案。如果无法到达最终状态,输出-1。

样例

输入

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

输出

6
-1

提示

给出的样例都是3*3,实际给出是一行9个数字,每个数字一个空格分开

时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题