原题地址：
POJ-3126
题意解释：
找到从素数A转换至素数B的最短方式（A,B都为四位数）
每次转换后的数字必须是四位素数，且每次只能改变四位数中的其中一位。
题目吐槽：
这个国王天天不理朝政，尽想着素数的破事，没事换个门牌还嫌贵，重点是不仅劳民伤财，还让我伤脑子！？我想写一句MMP贴你门牌上！你们就不能做一个四位数的门牌一下拍上去？？
解决方案：
空降坐标：60%
既然看到了素数，还要反复查询，不说别的，欧拉筛先码上，然后我们就能愉快的O(1)查素数了。
vector<bool> prime;
void makeprime(int n){prime.resize(n,1);vector<int> pi;for(unsigned int i=2;i!=prime.size();++i){if(prime[i]){pi.push_back(i);}for(unsigned int j=0;j!=pi.size();++j){if(pi[j]*i>prime.size()){break;}prime[i*pi[j]]=0;if(i%pi[j]==0){break;}}}
}虽然什么都不懂，但是欧拉筛码出来了。
可以了，本次的题解就愉快的结束了。
End。
好的。聪明的人都知道这么多空白肯定有问题，毕竟进度条暴露了坐标。
题解正式开始
此题使用BFS，首先将第一个素数放入一个自建的类型中，自建类型的功能是记录转换到这个素数需要的步数，然后把这个元素放入队列，然后开始循环。
每次循环时需要从队列中取出一个元素，循环得到这个数字能得到的所有四位数，去掉不是素数的，去掉以前计算过的（用数组标记哪些数字已经进入过队列），把剩下的放入队列（步数加一）。当然如果直接得到目标素数了，就返回步数加一就好。
贴上自己的代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<string>
using namespace std;
vector<bool> prime;
void makeprime(int n){prime.resize(n,1);vector<int> pi;for(unsigned int i=2;i!=prime.size();++i){if(prime[i]){pi.push_back(i);}for(unsigned int j=0;j!=pi.size();++j){if(pi[j]*i>prime.size()){break;}prime[i*pi[j]]=0;if(i%pi[j]==0){break;}}}
}
class mynum{
public:string num;int step;mynum(){num="";step=0;}mynum(string a,int b){num=a;step=b;}
};
int calc(string &a){int ans=0;for(unsigned int i=0;i!=a.size();i++){ans=ans*10;ans+=a[i]-'0';}return ans;
}
int core(string &a,string &b){if(a==b){return 0;}int tag=calc(b);vector<bool> flag;flag.resize(10000,0);flag[tag]=1;queue<mynum> TT;TT.push(mynum(a,0));while(!TT.empty()){mynum val=TT.front();TT.pop();flag[calc(val.num)]=1;for(int i=0;i!=4;i++){int r=val.num[i];int j=0;if(i==0){j=1;}for(;j!=10;j++){val.num[i]=j+'0';int n=calc(val.num);if(prime[n]){if(!flag[n]){TT.push(mynum(val.num,val.step+1));}if(n==tag){return val.step+1;}}}val.num[i]=r;}}}
int main(){makeprime(10000);int T;cin>>T;while(T--){string a,b;cin>>a>>b;cout<<core(a,b)<<endl;}return 0;
}
//Designed by wolf