#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<stack>
#define ll long long
#define N 200000
#include<math.h>
#include<queue>
using namespace std;
bool biaoji[10000];
bool p[10500];
struct node{
int v;
int step;
};
node start;
queue<node>que;
int goal;
int cifang(int n){
int ans=1;
for(int i=0;i<n;i++){
    ans*=10;
}
return ans;
}
int gaibian(int x,int k,int j){
int jianshu=(x/cifang(k))%10*cifang(k);
return x-jianshu+j*cifang(k);
}
int main(){
    freopen("input2.txt","r",stdin);
    for(int i=1;i<=9999;i++){
    p[i]=1;
}
p[1]=0;
for(int i=2;i<9999/2;i++){
    for(int j=2;j<=9999/i;j++){
        p[j*i]=0;
    }
}


int t;
cin>>t;
for(int i=0;i<t;i++){
        memset(biaoji,0,sizeof(biaoji));
        int l;
scanf("%d%d",&start.v,&goal);
    while(!que.empty())que.pop();
    start.step=0;
    biaoji[start.v]=1;
    que.push(start);
    while(!que.empty()){
        node now=que.front();
        que.pop();
        if(now.v==goal){
            cout<<now.step<<endl;
            break;
        }
        biaoji[now.v]=1;
       for(int k=0;k<4;k++) {
        for(int j=0;j<=9;j++){
            if(k==3&&j==0)continue;
            int xiayige=gaibian(now.v,k,j);
            if(p[xiayige]&&!biaoji[xiayige]){
                node next;
                next.v=xiayige;
                next.step=now.step+1;
                que.push(next);
            }
        }
       }
    }

}
  return 0;
}