非常水的一道广搜题（专业刷水题）。

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#define inf 1000000

using namespace std;

int d[4]={1,10,100,1000};

int vis[10000];

int prime[10000];

int q[inf];

int n1,n2;

void isprime()

{

    memset(prime,1,sizeof prime);

    for(int i=2;i<10000;i++){

        if(prime[i]){

            for(int j=i*i;j<10000;j+=i){

                prime[j]=0;

            }

        }

    }

}

void bfs()

{

    int front=0,rear=0;

    memset(q,0,sizeof(q));

    memset(vis,0,sizeof( vis));

    vis[n1]=1;

    q[rear++]=n1;

    while(front<rear){

        int cur=q[front++];

        for(int i=0;i<4;i++){

            int t[4];

            t[3]=cur/1000,t[2]=cur/100%10,t[1]=cur/10%10,t[0]=cur%10;

            for(int j=0;j<=9;j++){

                if(j==t[i]) continue;

                if(i==3&&j==0) continue;

                else{

                    int next=(cur-t[i]*d[i])+j*d[i];

                    if(prime[next]&&!vis[next]){

                        if(next==n2){

                            cout<<vis[cur]<<endl;return;

                        }

                        else{

                            vis[next]=vis[cur]+1;

                            q[rear++]=next;

                        }

                    }

                }

            }

        }

    }

    cout<<"0"<<endl;

}

int main()

{

    isprime();

    int T;

    cin>>T;

    while(T--){

        cin>>n1>>n2;

        bfs();

    }

    return 0;

}