1017 - 拼图
时间限制 : 1 秒
内存限制 : 256 MB
拼图游戏由一个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个数字，每个数字一个空格分开