#include<iostream>
#include<string.h>
using namespace std;
bool prime[10000];    
bool isUse[10000];       
char num1[5],num2[5];    
int a,b;                      
int ans;      
struct State
{
	char num[5];
};
State qu[1229];  
int qs,qt,qly;
void init(void)
{
	int i,j;
	memset(prime,true,sizeof(prime));
	prime[1]=false;

	for(i=2; i<100; i++)
	{
		if(prime[i])
		{
			for(j=2*i; j<10000; j+=i)
			{
				prime[j]=false;
			}
		}
	}
}
void BFS(void)
{
	int i,j;
	int convert_num;
	char temp_num[5];
	char temp_ch;
	strcpy(qu[0].num,num1);
	qs=0; qt=1;
	qly=qt-1;
	while(qs<qt)
	{
		if(qs>qly)
		{
			ans++;
			qly=qt-1;
		}
		strcpy(temp_num,qu[qs].num);
		for(i=0;i<4;i++)
		{
			temp_ch=temp_num[i];

			for(j=0;j<10;j++)
			{

				if(temp_num[i]==j+'0')
					continue;
			
				temp_num[i]=j+'0';
				if(temp_num[0]=='0')
					continue;
				if((temp_num[3]-'0')%2==0)
					continue;

				if(strcmp(temp_num,num2)==0)
				{
					ans++;
					return;
				}
				convert_num=temp_num[3]-'0'+(temp_num[2]-'0')*10+(temp_num[1]-'0')*100+(temp_num[0]-'0')*1000;
				if(isUse[convert_num]==false && prime[convert_num]==true)
				{

					isUse[convert_num]=true;
					strcpy(qu[qt].num,temp_num);
					qt++;
				}
			}

			temp_num[i]=temp_ch;
		}
		qs++;
	}
}
int main(void)
{
	int test_num;
	int i;
	cin>>test_num;
	init();   
	while(test_num--)
	{
		cin>>num1>>num2;
		ans=0;
		if(strcmp(num1,num2)!=0)
		{
			memset(isUse,false,sizeof(isUse));
			BFS();
		}
		cout<<ans<<endl;
	}
}