描述
孤单的zydsg又一次孤单的度过了520，不过下一次不会再这样了。zydsg要做些改变，他想去和素数小姐姐约会。
所有的路口都被标号为了一个4位素数，zydsg现在的位置和素数小姐姐的家也是这样，如果两个路口间只差1个数字，则有一条路连通两个路口。（例如1033和1073间有一条路连接）
现在，你知道了zydsg的位置和素数小姐姐的家，问最少zydsg要走多少条路才能见到素数小姐姐。例如：如果zydsg在1033，素数小姐姐的家在8179，最少要走6条街，走法为：
Input
输入数据有多组，首先是一个数字n，代表之后有n组数据。
其次，在每一组输入中，都包含两个数字a和b，代表zydsg的位置和素数小姐姐家的位置。
其中，a和b都是四位数，而且不含前导0。
其次，在每一组输入中，都包含两个数字a和b，代表zydsg的位置和素数小姐姐家的位置。
其中，a和b都是四位数，而且不含前导0。
Output
每组输入输出一行，表示zydsg最少需要走多少条路。若不存在合法的路径，则输出单词“Impossible”。Sample Input
3
1033 8179
1373 8017
1033 1033
Sample Output
6
7
0
分析
首先我们要筛素数，接下来
方法一：
两个“相邻的”素数连边，每次从开头向终点跑SPFA
方法二：
按个十百千位向四周扩散，BFS
代码（SPFA）
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;++i)
#define per(i,a,b) for(RG i=a;i>=b;--i)
#define ll long long
#define inf (1<<29)
#define maxn 10005
#define lim 10002
#define maxm 1500005
#define add(x,y) e[++ct]=(E){y,head[x]},head[x]=ct
using namespace std;
int n,m,cnt,ct;
int isp[maxn],p[maxn],head[maxn],dis[maxn],vis[maxn],id[maxn];
struct E{
int v,next;
}e[maxm];
inline int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline int judge(int x,int y)
{
int sum=;
while(x) {if(x%!=y%) sum++;x/=,y/=;}
return sum==;
} void pre()
{
rep(i,,lim)
{
if(!isp[i]) p[++cnt]=i,id[i]=cnt;
for(RG j=;j<=cnt&&p[j]*i<=lim;j++)
{
isp[i*p[j]]=;
if(!(i%p[j])) break;
}
}
rep(i,,cnt) rep(j,i+,cnt) if(judge(p[i],p[j])) add(i,j),add(j,i);
} int SPFA(int S,int T)
{
memset(dis,,sizeof(dis));dis[S]=;
queue<int> que;que.push(S);
RG u,v;
while(!que.empty())
{
u=que.front(),que.pop(),vis[u]=;
for(RG i=head[u];i;i=e[i].next)
{
v=e[i].v;
if(dis[v]>dis[u]+){
dis[v]=dis[u]+;
if(!vis[v]) vis[v]=,que.push(v);
}
}
}
return dis[T];
} int main()
{
int Tim=read();
pre();
while(Tim--)
{
scanf("%d%d",&n,&m);
printf("%d\n",SPFA(id[n],id[m]));
}
return ;
}