> //6266010 on_pku 3126 Accepted 732K 16MS G++ 2214B 2009-12-21 18:18:46 
> #include<iostream>
> #include<cstdlib>
> #include<cstdio>
> #include<queue>
> using namespace std;
> const int SIZE = 10000;
> bool prime[SIZE];
> int step[SIZE];
> int base[4] = {1,10,100,1000};
> int main()
> {
>         for(int i = 0; i < SIZE; i++)prime[i] = true;
>         
>         for(int i = 2; i < SIZE; i++){
>                 if(prime[i]){
>                              for(int j = 2; i*j < SIZE; j++)
>                                      prime[i*j] = false;             
>                 }        
>         }
>         
>         int t,a,b,d[4];
>         scanf("%d",&t);
>         while(t--){
>                    scanf("%d %d",&a,&b);
>                    fill(step,step+SIZE,0);
>                    queue<int>path;
>                    path.push(a);
>                    step[a] = 1;
>                    while(!path.empty()){
>                          int ori = path.front();
>                          if(ori == b)break;
>                          path.pop();
>                          d[0] = ori%10;  d[1] = ori%100/10;
>                          d[2] = ori%1000/100;  d[3] = ori/1000;
>                          int newnum;
>                          for(int i = 0; i < 10; i ++){                                                   
>                                  newnum = ori - d[3]*1000 + i*1000;
>                                  if(i != 0 && prime[newnum] && !step[newnum]){
>                                       step[newnum] = step[ori] + 1;
>                                       path.push(newnum);               
>                                  } 
>                                  for(int k = 0; k < 3; k++){
>                                          newnum = ori - d[k]*base[k] + i*base[k];
>                                          if(prime[newnum] && !step[newnum]){
>                                               step[newnum] = step[ori] + 1;
>                                               path.push(newnum);               
>                                          }                               
>                                  }  
>                          }                     
>                    }     
>                    printf("%d\n",step[b]-1);
>         }        
>         return 0;
> }