1 #include <cstdio>  2 #include <cstring>  3 #include <cstdlib>  4 #include <cmath>  5 #include <cctype>  6 #include <time.h>  7 #include <string>  8 #include <set>  9 #include <map> 10 #include <queue> 11 #include <vector> 12 #include <stack> 13 #include <algorithm> 14 #include <iostream> 15 #define PI acos( -1.0 ) 16 using namespace std; 17 typedef long long ll; 18 typedef pair<int,int> P; 19 const double E = 1e-8; 20  21 const int NO = 100005; 22 int n, m, cur = 0; 23 int p[105]; 24 int step[NO]; 25 struct ND 26 { 27     int s1[5]; 28 }a, b; 29  30 void prime() 31 { 32     memset( p, 0, sizeof( p ) ); 33     p[cur++] = 2; 34     for( int i = 3; i <= 100; ++i ) 35     { 36         bool flag = true; 37         for( int j = 2; j*j <= i; ++j ) 38             if( i % j == 0 ) { 39                 flag = false; 40                 break; 41             } 42         if( flag ) 43             p[cur++] = i; 44     } 45 } 46  47 bool Isprime( int x ) 48 { 49     if( x <= 1 ) 50         return false; 51     if( x == 2 ) 52         return true; 53     for( int i = 0; i < cur && p[i]*p[i] <= x; ++i ) 54         if( x % p[i] == 0 ) 55             return false; 56     return true; 57 } 58  59 void init() 60 { 61     a.s1[0] = n / 1000; 62     a.s1[1] = n % 1000 / 100; 63     a.s1[2] = n / 10 % 10; 64     a.s1[3] = n % 10; 65 } 66  67 int cnt( ND t ) 68 { 69     int num = 0; 70     for( int i = 0; i < 4; ++i ) 71         num = num * 10 + t.s1[i]; 72     return num; 73 } 74  75 void bfs() 76 { 77     memset( step, -1, sizeof( step ) ); 78     queue <ND> q; 79     step[n] = 0; 80     q.push( a ); 81     while( !q.empty() ) 82     { 83         b = q.front(); q.pop(); 84         int t = cnt( b ); 85         for( int i = 0; i < 4; ++i ) 86         { 87             int x = b.s1[i]; 88             for( int j = 0; j <= 9; ++j ) 89             { 90                 if( i == 0 && j == 0 ) continue; 91                 if( j == x ) continue; 92                 b.s1[i] = j; 93                 int y = cnt( b ); 94                 if( step[y] == -1 && Isprime( y ) ) 95                 { 96                     step[y] = step[t] + 1; 97                     if( y == m ) 98                     { 99                         printf( "%d\n", step[y] );100                         return;101                     }102                     q.push( b );103                 }104             }105             b.s1[i] = x;106         }107     }108     puts( "Impossible" );109 }110 111 int main()112 {113     int T;114     scanf( "%d", &T );115     prime();116     while( T-- )117     {118         scanf( "%d%d", &n, &m );119         if( n == m ) {120             puts( "0" );121             continue;122         }123         init();124         bfs();125     }126     return 0;127 }