#include<iostream>
#include<math.h>
using namespace std;
struct lift
{
    int k,n;
}key[3000];
int N,B,i,j,x,k[9001],m,ii,jj,t;
int panduan(int x)
{
	int a=sqrt(double(x));
	for(jj=2;jj<=a&&x%jj!=0;jj++);
	if(jj>=a+1) return 1;
	else return 0;
}
int bfs()
{
	memset(k,0,sizeof(k));
	key[0].n=0;
	i=0;
	j=1;
	while(i<j)
	{
		for(ii=1;ii<1001;ii*=10)
		{
			t=(key[i].k/(ii*10))*(ii*10)+key[i].k%ii;
			if(ii!=1000) m=0;
			else m=1;
			for(;m<10;m++)
			{
				x=t+m*ii;
				if(x!=key[i].k&&panduan(x)) 
				{
					if(x==B) return key[i].n;
					if(x<10000&&!k[x-1000]) 
					{
						key[j].k=x;
						k[x-1000]=1;
						key[j++].n=key[i].n+1;
					}
				}
			}
		}
		i++;
	}
}
int main()
{
    scanf("%d",&N);
	while(N-->0&&N<101&&scanf("%d%d",&key[0].k,&B)!=EOF)
	{
		if(key[0].k==B) printf("0\n");
		else 	
		{
			if(key[0].k>B)
			{
				t=key[0].k;
				key[0].k=B;
				B=t;
			}
            printf("%d\n",bfs()+1);
		}
	}
	return 0;
}