#include<stdio.h>
//#include<iostream.h>
//#include<conio.h>
//#include<conio.h>
int a[10001],v[1062][1062],n,k,n1,n2,el;

void sir(){
	 int i,j;
	 for(i=2;i<=5000;i++)
	      if(a[i]==0)
		for(j=2*i;j<=10000;j=j+i) a[j]=1;

	 for(i=1000;i<=10000;i++)
		 if(a[i]==0) a[++k]=i;
			}
int cifra(int x,int y){
	    int a1[5],a2[5],ok=0;

	     a1[4]=x%10;
	     x/=10;
	     a1[3]=x%10;
	     x/=10;
	     a1[2]=x%10;
	     x/=10;
	     a1[1]=x%10;

	     a2[4]=y%10;
	     y/=10;
	     a2[3]=y%10;
	     y/=10;
	     a2[2]=y%10;
	     y/=10;
	     a2[1]=y%10;

	     for(int i=1;i<5;i++)
		  if(a1[i]!=a2[i]) ok++;
	     return ok;
	     }

void rf(){
	int i,j,l;

       for(l=1;l<=k;l++)
	for(i=1;i<=k;i++)
	 for(j=1;j<=k;i++)
	    if(v[i][l]+v[l][j]<v[i][j]) v[i][j]=v[i][l]+v[l][j];
	}



void caut(int st,int dr,int &z){

	  int m;
	  if(dr>st){
		    m=(st+dr)/2;
		    if(a[m]==el) z=m;
		     else
			if(el>a[m]) caut(m+1,dr,z);
			 else caut(st,m,z);
		       }
	  }




int main(){
int i,j,n,z;
clrscr();

//freopen("ppath.in","w",stdin);
//freopen("ppath.out","r",stdout);

sir();

//for(i=1;i<100;i++) cout<<a[i]<<" ";  1031 -> 1231


for(i=1;i<k;i++)
 for(j=i+1;j<=k;j++)
	 if(cifra(a[i],a[j])==1) { v[i][j]=1;
				   v[j][i]=1;
				    }

rf();

scanf("%ld",&n);
for(i=1;i<=n;i++){
		//int n1,n2;
		scanf("%ld %ld",&n1,&n2);

		if(n1==n2) printf("0\n");
		else{
		el=n1;z=0;
		caut(1,k,z);n1=z+1;
		el=n2;z=0;
		caut(1,k,z);n2=z+1;
		printf("%ld\n",v[n1][n2]);
		 }
		 }  

return 0;
}