> #include <iostream>
> #include <cstdio>
> #include <cstring>
> #include <algorithm>
> #include <cmath>
> #include <set>
> #include <queue>
> using namespace std;
> 
> #define mem(a) memset(a,0,sizeof(a))
> #define ll long long
> const int maxn = 100100;
> const int inf = 0x3f3f3f3f;
> int t,n,m;
> bool vis[10000];
> set<int> a;
> void init()
> {
>     int i,j,k=0;
>     for(i = 1001; i < 10000; i+=2)
>     {
>         for(j = 2; j <= sqrt(i); j++)
>         {
>             if(i%j == 0) break;
>         }
>         if(j > sqrt(i)) a.insert(i);
>     }
> }
> 
> struct node
> {
>     int num,step;
> };
> 
> void bfs()
> {
>     mem(vis);
>     node x,y;
>     vis[n] = 1;
>     x.num = n,x.step = 0;
>     queue <node> q;
>     q.push(x);
>     while(!q.empty())
>     {
>         x = q.front();
>         q.pop();
>         if(x.num == m)
>         {
>             printf("%d\n",x.step);
>         }
>         int ge  = x.num-x.num%10;
>         int shi = x.num - (x.num%100-x.num%10);
>         int bai = x.num - (x.num%1000/100)*100;
>         int qi  = x.num%1000;
>         for(int i = 1; i <10 ; i+=2)
>         {
>             y.num = ge+i;
>             if(a.count(y.num) && !vis[y.num])
>             {
>                 y.step = x.step+1;
>                 vis[y.num] = 1;
>                 q.push(y);
>             }
>         }
>         for(int i = 0; i <10 ; i++)
>         {
>             y.num = shi+i*10;
>             if(a.count(y.num) && !vis[y.num])
>             {
>                 y.step = x.step+1;
>                 vis[y.num] = 1;
>                 q.push(y);
>             }
>         }
>         for(int i = 0; i <10 ; i++)
>         {
>             y.num = bai+i*100;
>             if(a.count(y.num) && !vis[y.num])
>             {
>                 y.step = x.step+1;
>                 vis[y.num] = 1;
>                 q.push(y);
>             }
>         }
>         for(int i = 1; i <10 ; i++)
>         {
>             y.num = qi+i*1000;
>             if(a.count(y.num) && !vis[y.num])
>             {
>                 y.step = x.step+1;
>                 vis[y.num] = 1;
>                 q.push(y);
>             }
>         }
>     }
> }
> 
> int main()
> {
>     //ios::sync_with_stdio(false);
>     //cin.tie(0),cout.tie(0);
>     init();
>     scanf("%d",&t);
>     while(t--)
>     {
>         scanf("%d%d",&n,&m);
>         bfs();
>     }
>     return 0;
> }