明早来看

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
bool flag=true,kkksc03,a[10000000];
struct node{
	int m;//数 
	int a;//千 
	int b;//百 
	int c;//十 
	int d;//个 
	int k;//次数 
};
queue<node>s;
void primecsh(){ 
	for(int i=1000;i<10000;i++){
  		flag=true;
  		for(int j=2;j*j<=i;j++){
  			if(i%j==0){
  				flag=false;
  				a[i]=false;
  				break;
			}
		}
		if(flag==true)a[i]=true;
	}
}
int qkdl(){
	while(!s.empty()){
		s.pop();
	}
}
int bfs(int k){
	kkksc03=false;
	while(!s.empty()){
		node f=s.front();
		if(f.m==k){
			cout<<f.k<<endl;
			kkksc03=true;
			break;
		}
		for(int i=1;i<=9;i++){
			if(i==f.a)
				continue;
			if(a[f.b*100+f.c*10+f.d+i*1000]==true)
				s.push((node){f.b*100+f.c*10+f.d+i*1000,i,f.b,f.c,f.d,f.k+1});
		}
			
		for(int i=0;i<=9;i++){
			if(i==f.b)
				continue;
			if(a[f.a*1000+f.c*10+f.d+i*100]==true)
				s.push((node){f.a*1000+f.c*10+f.d+i*100,f.a,i,f.c,f.d,f.k+1});	
		}
		for(int i=0;i<=9;i++){
			if(i==f.c)
				continue;
			if(a[f.a*1000+f.b*100+f.d+i*10]==true)
				s.push((node){f.a*1000+f.b*100+f.d+i*10,f.a,f.b,i,f.d,f.k+1});	
		}
			
		for(int i=0;i<=9;i++){
			if(i==f.d)
				continue;
			if(a[f.a*1000+f.b*100+f.c*10+i]==true)
				s.push((node){f.a*1000+f.b*100+f.c*10+i,f.a,f.b,f.c,i,f.k+1});
		}
			
		s.pop();
	}
	
}
int main(){
  	primecsh();
  	cin>>n;
  	for(int i=1;i<=n;i++){
  		cin>>m>>k;
  		s.push((node){m,m/1000,m/100%10,m/10%10,m%10,0});
  		bfs(k);
  		if(kkksc03==false){
  			cout<<"Impossible"<<endl;
		}
		qkdl();
	}
    return 0;
}