【题意】给定两个4位的质数a和b，从a开始每次只能改变a的一个数字，并且改完后的a还是质数，求a最少经过几次变换能得到b.....

 比如1033变到8179最少需要6次，过程如下

1033
1733
3733
3739
3779
8779
8179

【分析】简单40入口bfs。

【AC代码】

#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int getInt(int &x)
{
    return scanf("%d",&x);
}
int is[10010];
int ans[10010];
bool vis[10010];
void init()
{
    memset(is,0,sizeof(is));
    is[1]=1;
    for(int i=2;i*i<=10010;i++)
    {
        if(!is[i])
        {
            for(int j=i*i;j<=10010;j+=i)
            {
                is[j]=1;
            }
        }
    }
}
 
int bfs(int a,int b)
{
    queue<int>qu;
    qu.push(a);
    ans[a]=0;
    vis[a]=true;
    while(!qu.empty())
    {
        int tmp=qu.front();
        qu.pop();
        for(int i=0;i<=9;i++)
        {
            int tmp1=(tmp/10)*10+i;//个位
            if(!is[tmp1]&&!vis[tmp1])
            {
                qu.push(tmp1);
                ans[tmp1]=ans[tmp]+1;
                vis[tmp1]=true;
            }
            int tmp2=(tmp/100)*100+tmp%10+i*10;//十位
            if(!is[tmp2]&&!vis[tmp2])
            {
                qu.push(tmp2);
                ans[tmp2]=ans[tmp]+1;
                vis[tmp2]=true;
            }
            int tmp3=(tmp/1000)*1000+tmp%100+i*100;//百位
            if(!is[tmp3]&&!vis[tmp3])
            {
                qu.push(tmp3);
                ans[tmp3]=ans[tmp]+1;
                vis[tmp3]=true;
            }
            if(i!=0)
            {
                  int tmp4=tmp%1000+i*1000;//千位，无前导0
                  if(!is[tmp4]&&!vis[tmp4])
                  {
                      qu.push(tmp4);
                      ans[tmp4]=ans[tmp]+1;
                      vis[tmp4]=true;
                  }
            }
            if(vis[b])return ans[b];
        }
    }
    return -1;
}
int main()
{
    int n,a,b;
    init();
    getInt(n);
    while(n--)
    {
        getInt(a);getInt(b);
        memset(ans,0,sizeof(ans));
        memset(vis,false,sizeof(vis));
        int ans=bfs(a,b);
        if(ans==-1)
            puts("Impossible");
        else
            printf("%d\n",ans);
    }
    return 0;
}