#include<stdio.h>
#include<string.h>
#define max 10000
int prime[10000],dui[1000000],flag[10000],opt[10000];
int a,b;

void primeform()
{
	int i,j;
	for(i=2;i<10000;i++)
	{
		for(j=2;j<5000;j++)
		{
			if(i*j<10000)
			{
				prime[i*j]=1;//表示合数
			}
		}
	}
}

void bfs(int a)
{
	int rear=0,front=0,i,p,q,k,r,y,yu,x;
	dui[rear]=a;
	flag[a]=1;
	opt[a]=0;
	front++;
	while(rear!=front)
	{
		x=dui[rear];
		rear++;
		p=x/1000;
		yu=x%1000;
		q=yu/100;
		yu=yu%100;
		r=yu/10;
		k=yu%10;
		for(i=p+1;i<10;i++)
		{
			y=i*1000+q*100+r*10+k;
			if(prime[y]==0&&flag[y]==0)
			{
				dui[front]=y;
                flag[y]=1;
				opt[y]=opt[x]+1;
				front++;
			}
			if(y==b)
			{
				printf("%d\n",opt[y]);
				return ;
			}
		}
		for(i=p-1;i>0;i--)
		{
			y=i*1000+q*100+r*10+k;
			if(prime[y]==0&&flag[y]==0)
			{
				dui[front]=y;
                flag[y]=1;
				opt[y]=opt[x]+1;
				front++;
			}
			if(y==b)
			{
				printf("%d\n",opt[y]);
				return ;
			}
		}
		for(i=q+1;i<10;i++)
		{
			y=p*1000+i*100+r*10+k;
			if(prime[y]==0&&flag[y]==0)
			{
				dui[front]=y;
                flag[y]=1;
				opt[y]=opt[x]+1;
				front++;
			}
			if(y==b)
			{
				printf("%d\n",opt[y]);
				return ;
			}
		}		
		for(i=q-1;i>=0;i--)
		{
			y=p*1000+i*100+r*10+k;
			if(prime[y]==0&&flag[y]==0)
			{
				dui[front]=y;
				flag[y]=1;
				opt[y]=opt[x]+1;
				front++;
			}	
			if(y==b)
			{
				printf("%d\n",opt[y]);
				return ;
			}
		}
		for(i=r+1;i<10;i++)
		{
			y=p*1000+q*100+i*10+k;
			if(prime[y]==0&&flag[y]==0)
			{
				dui[front]=y;
                flag[y]=1;
				opt[y]=opt[x]+1;
				front++;
			}
			if(y==b)
			{
				printf("%d\n",opt[y]);
				return ;
			}
		}		
		for(i=r-1;i>=0;i--)
		{
			y=p*1000+q*100+i*10+k;
			if(prime[y]==0&&flag[y]==0)
			{
				dui[front]=y;
				flag[y]=1;
				opt[y]=opt[x]+1;
				front++;
			}
			if(y==b)
			{
				printf("%d\n",opt[y]);
				return ;
			}
		}
		for(i=k+1;i<10;i++)
		{
			y=p*1000+q*100+r*10+i;
			if(prime[y]==0&&flag[y]==0)
			{
				dui[front]=y;
                flag[y]=1;
				opt[y]=opt[x]+1;
				front++;
			}
			if(y==b)
			{
				printf("%d\n",opt[y]);
				return ;
			}
		}		
		for(i=k-1;i>=0;i--)
		{
			y=p*1000+q*100+r*10+i;
			if(prime[y]==0&&flag[y]==0)
			{
				dui[front]=y;
				flag[y]=1;
				opt[y]=opt[x]+1;
				front++;
			}
			if(y==b)
			{
				printf("%d\n",opt[y]);
				return ;
			}
		}
	}

}
int main()
{
	int i,n;
	memset(prime,0,sizeof(prime));
	primeform();
	/*for(i=1000;i<10000;i++)
	{
	if(prime[i]==0)
	{
	printf("%d ",i);
	}
	}
	printf("\n");*/
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		memset(flag,0,sizeof(flag));
		memset(opt,0,sizeof(opt));
		scanf("%d%d",&a,&b);
		bfs(a);
	}
	
	return 0;
}