1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int n,x,y; 7 bool v[20000]; 8 struct point 9 {10     int x;11     int step;12 };13 14 int change(int x,int y,int z)15 {16     if (z==4) return (x/10)*10+y;17     else if (z==3)18     {19         int t=y*10+x%10;20         return (x/100)*100+t;21     }22     else if (z==2)23     {24         int t=y*100+x%100;25         return (x/1000)*1000+t;26     }27     else if (z==1)28     {29         return y*1000+(x%1000);30     }31 }32 33 bool prime(int x)34 {35     if (x==2 || x==3) return true;36     if (x<=1 || x%2==0) return false;37     for (int i=3;i<=sqrt(x);i++)38         if (x%i==0) return false;39     return true;40 }41 42 void bfs(int sx,int ex)43 {44     memset(v,0,sizeof(v));45     queue<point>que;46     point now,next;47     now.x=sx;48     now.step=0;49     v[sx]=1;50     que.push(now);51     while (!que.empty())52     {53         now=que.front();54         que.pop();55         if (now.x==ex)56         {57             printf("%d\n",now.step);58             return ;59         }60 61         for (int i=0;i<=9;i++)62             for (int j=1;j<=4;j++)63             {64                 if (i==0 && j==1) continue;65                 next.x=change(now.x,i,j);66                 if (prime(next.x) && !v[next.x])67                 {68                     v[next.x]=1;69                     next.step=now.step+1;70                     que.push(next);71                 }72             }73 74     }75     printf("Impossible\n");76 }77 int main()78 {79     scanf("%d",&n);80     for (int t=1;t<=n;t++)81     {82         scanf("%d%d",&x,&y);83         bfs(x,y);84     }85     return 0;86 }