方老师与素数

#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14const int N=2e5+10,M=1e6+10,inf=1e9+10,mod=1e9+7;const ll INF=1e18+10;int p[1110];int prime(int n){    if(n<=1)    return 0;    if(n==2)    return 1;    if(n%2==0)    return 0;    int k, upperBound=n/2;    for(k=3; k<=upperBound; k+=2)    {        upperBound=n/k;        if(n%k==0)            return 0;    }    return 1;}int check(int x,int y){    int sum=0;    while(x)    {        if(x%10!=y%10)sum++;        x/=10;        y/=10;    }    return sum;}int flag[10010];struct is{    int num;    int ans;    is(){}    is(int x,int y)    {        num=x;        ans=y;    }};int main(){    int cnt=0;    for(int i=1000;i<=10000;i++)    if(prime(i))    p[cnt++]=i;    int T;    scanf("%d",&T);    while(T--)    {        for(int i=0;i<cnt;i++)            flag[p[i]]=0;        int n,m;        scanf("%d%d",&n,&m);        flag[n]=1;        queue<is>q;        q.push(is(n,0));        int out=inf;        while(!q.empty())        {            is v=q.front();            q.pop();            if(v.num==m)            {                out=v.ans;                break;            }            for(int i=0;i<cnt;i++)            {                if(!flag[p[i]]&&check(v.num,p[i])==1)                {                    flag[p[i]]=1;                    q.push(is(p[i],v.ans+1));                }            }        }        if(out!=inf)        printf("%d\n",out);        else            printf("Impossible\n");    }    return 0;}