1818: [NewOJ Week 6] 质数拼图游戏
内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：103
通过：54
题目描述
拼图游戏由一个3×3的棋盘和数字1-9组成。目标是达到以下最终状态：
1 2 3
4 5 6
7 8 9
每次如果相邻两个数字之和为质数，则可以进行交换。
相邻：上下左右四联通
给定一个棋盘初始状态，求到达最终状态的最短步数。
1 2 3
4 5 6
7 8 9
每次如果相邻两个数字之和为质数，则可以进行交换。
相邻：上下左右四联通
给定一个棋盘初始状态，求到达最终状态的最短步数。
输入格式
第一行为正整数T，表示存在T组测试数据，1≤T≤50。
对于每组测试数据，输入3行，每行3个数字表示棋盘。
输入保证合法，棋盘中的9个数字仅为1-9。
对于每组测试数据，输入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数据范围与提示
第一组测试数据的6步如下：
