题干：

给你两个四位的素数a，b。
a可以改变某一位上的数字变成c，但只有当c也是四位的素数时才能进行这种改变。
请你计算a最少经过多少次上述变换才能变成b。
例如：1033 -> 8179 
1033 
1733 
3733 
3739 
3779 
8779 
8179
最少变换了6次。

Input

第一行输入整数T，表示样例数。 (T <= 100) 
每个样例输入两个四位的素数a，b。(没有前导零) 

Output

对于每个样例，输出最少变换次数，如果无法变换成b则输出"Impossible"。

Sample Input

3
1033 8179
1373 8017
1033 1033

Sample Output

6
7
0

解题报告：

  期末复习前最后一水题，博客停更。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e4 + 5;
int a[5],tmp[5]; 
bool vis[MAX];
bool is[MAX];
void prime() {
	memset(is,1,sizeof is);
	is[1]=is[0]=1;
	for(int i = 2; i<=20000; i++) {
		if(is[i] == 0) continue;
		for(int j = i+i; j<=20000; j+=i) is[j] = 0;
	}
}
void get(int x) {
	int p = 0;
	while(x) {
		a[++p] = x%10;
		x/=10;
	}
}
int go() {
	int res = 0 ;
	for(int i = 4; i>=1; i--) {
		res = res * 10 + tmp[i];
	}
	return res;
}
void init() {
	for(int i = 1; i<=4; i++) tmp[i] = a[i];
}
struct Node {
	int val,t;
	Node(int val=0,int t=0):val(val),t(t){}
};
int bfs(int st,int ed) {
	queue<Node> q;
	q.push(Node(st,0));
	while(q.size()) {
		Node cur = q.front();q.pop();
		get(cur.val);
		if(cur.val == ed) return cur.t;
		init();
		for(int i = 0; i<=9; i++) {
			tmp[1] = i;
			if(is[go()] && vis[go()] == 0) {
				vis[go()] = 1;
				q.push(Node(go(),cur.t + 1));
			} 
		}
		init();
		for(int i = 0; i<=9; i++) {
			tmp[2] = i;
			if(is[go()] && vis[go()] == 0) {
				vis[go()] = 1;
				q.push(Node(go(),cur.t + 1));
			} 
		}
		init();
		for(int i = 0; i<=9; i++) {
			tmp[3] = i;
			if(is[go()] && vis[go()] == 0) {
				vis[go()] = 1;
				q.push(Node(go(),cur.t + 1));
			} 
		}
		init();
		for(int i = 1; i<=9; i++) {
			tmp[4] = i;
			if(is[go()] && vis[go()] == 0) {
				vis[go()] = 1;
				q.push(Node(go(),cur.t + 1));
			} 
		}
	}
	return -1;
} 
int main()
{
	prime();
	int t,x,y;
	cin>>t;
	while(t--) {
		memset(vis,0,sizeof vis);
		cin>>x>>y;
		printf("%d\n",bfs(x,y));
	}
	return 0 ;
}
//20:55-21:07