题解【高速】

#include <bits/stdc++.h>
using namespace std;
vector<int> ve[10009];//ve[i]里存储i的邻居
bool prime[10009],vis[10009];//prime[i]=true表示不是素数  vis[i]=true表示i访问过 
void init(){
	prime[1]=1;
	for(int i=2;i<=9999;i++){
		if(!prime[i]){//判断i是否是素数 
			for(int j=2*i;j<=9999;j+=i) {//将i的倍数筛掉 
				prime[j]=1;
			}
		}
	}
	for(int i=1000;i<=9999;i++){//预处理除i的邻居 
		if(prime[i]) continue;//i不是素数，不需要预处理不是素数的邻居
		//千位数字变化
		for(int j=1;j<=9;j++){//千位数字变成j 
			int tem=i-i/1000*1000+j*1000;//把i的千位换成j
			if(tem!=i&&!prime[tem]){//tem想要当i的邻居必须不等于i且是素数 
				ve[i].push_back(tem);
			}
		}
		//百位数字变化
		for(int j=0;j<=9;j++){//百位数字变成j 
			int tem=i-i/100%10*100+j*100;//把i的百位换成j
			if(tem!=i&&!prime[tem]){//tem想要当i的邻居必须不等于i且是素数 
				ve[i].push_back(tem);
			}
		} 
		//十位数字变化
		for(int j=0;j<=9;j++){//十位数字变成j 
			int tem=i-i/10%10*10+j*10;//把i的十位换成j
			if(tem!=i&&!prime[tem]){//tem想要当i的邻居必须不等于i且是素数 
				ve[i].push_back(tem);
			}
		} 
		//个位数字变化
		for(int j=0;j<=9;j++){//个位数字变成j 
			int tem=i-i%10+j;//把i的个位换成j
			if(tem!=i&&!prime[tem]){//tem想要当i的邻居必须不等于i且是素数 
				ve[i].push_back(tem);
			}
		}
	}
}
struct node{
	int num,step;//num是当前所处的地板编号为num,step是到达num需要的步数 
};
int W; 
//返回从x开始到W需要的步数，到达不了返回0
int bfs(int x){
	queue<node> q;
	q.push({x,0});
	vis[x]=1;//标记x访问过 
	while(q.size()){
		node r=q.front();
		q.pop();
		if(r.num==W) return r.step;//在取队首的时候判断是否是终点
		for(int i=0;i<ve[r.num].size();i++){
			int y=ve[r.num][i];//y是r.num的邻居
			if(!vis[y]){//判断y是否被访问过 
				q.push({y,r.step+1});//将y放进队列 
				vis[y]=1;//标记y访问过
			} 
		} 
	}
	return 0;
}
int main() {
	init(); 
	int t;
	cin>>t;
	while(t--){
		memset(vis,0,sizeof(vis));
		int Q;
		cin>>Q>>W;
		cout<<bfs(Q)<<'\n'; 
	}
	return 0;
}