1 //Accepted    212 KB    16 ms  2 //筛素数+bfs  3 #include <cstdio>  4 #include <cstring>  5 #include <iostream>  6 #include <queue>  7 using namespace std;  8 const int inf = 100000000;  9 const int imax_n = 10005; 10 bool pri[imax_n]; 11 bool vis[imax_n]; 12 void prime() 13 { 14     for (int i=2;i<imax_n;i++) 15     { 16         for (int j=i*i;j<imax_n;j+=i) 17         { 18             pri[j]=1; 19         } 20     } 21     pri[0]=pri[1]=1; 22 } 23 queue<int > q,step; 24 int ans; 25 void bfs(int s,int e) 26 { 27     while (!q.empty()) q.pop(); 28     while (!step.empty()) step.pop(); 29     memset(vis,false,sizeof(vis)); 30     ans=inf; 31     q.push(s); 32     vis[s]=true; 33     step.push(0); 34     while (!q.empty()) 35     { 36         int x=q.front(); 37         q.pop(); 38         int temp_step=step.front(); 39         step.pop(); 40         if (x==e) 41         { 42             ans=temp_step; 43             return ; 44         } 45         int t=x%1000; 46         for (int i=1;i<=9;i++) 47         { 48             int nx=t+i*1000; 49             if (pri[nx]==0 && !vis[nx]) 50             { 51                 q.push(nx); 52                 step.push(temp_step+1); 53                 vis[nx]=true; 54             } 55         } 56         t=(x%1000)%100+x/1000*1000; 57         for (int i=0;i<=9;i++) 58         { 59             int nx=t+i*100; 60             if (pri[nx]==0 && !vis[nx]) 61             { 62                 q.push(nx); 63                 step.push(temp_step+1); 64                 vis[nx]=true; 65             } 66         } 67         t=x/100*100+x%100%10; 68         for (int i=0;i<=9;i++) 69         { 70             int nx=t+i*10; 71             if (pri[nx]==0 && !vis[nx]) 72             { 73                 q.push(nx); 74                 step.push(temp_step+1); 75                 vis[nx]=true; 76             } 77         } 78         t=x/10*10; 79         for (int i=1;i<=9;i+=2) 80         { 81             int nx=t+i; 82             if (pri[nx]==0 && !vis[nx]) 83             { 84                 q.push(nx); 85                 step.push(temp_step+1); 86                 vis[nx]=true; 87             } 88         } 89     } 90 } 91 int main() 92 { 93     prime(); 94     int T; 95     scanf("%d",&T); 96     while (T--) 97     { 98         int a,b; 99         scanf("%d%d",&a,&b);100         bfs(a,b);101         if (ans==inf)102         printf("Impossible\n");103         else104         printf("%d\n",ans);105     }106     return 0;107 }