#include<iostream>
#include <cstring>
#include <queue>
using namespace std;
queue<int>num;
const int N = 25600000;
bool a[N];
int p[N],step[10000];
int n;
void Prime2() 
{
	memset(a, 0, n*sizeof(a[0]));
	int num = 0, i, j;
	for(i = 2; i < n; ++i) 
	{
		if(!(a[i])) p[num++] = i;
		for(j = 0; (j<num && i*p[j]<n); ++j) 
		{
			a[i*p[j]] = 1;
			if(!(i%p[j])) break;
		}
	}
	a[0]=true,a[1]=true;
}

int pow(int x,int y)
{
	int sum=0;
	if(y==0)return 1;
	int t=1;
	while(y--){ t*=x; sum+=t;}
	return sum;
}
int main()
{
	n=10000;
	Prime2();
	int T;
	cin>>T;
	int aa,bb;
	while(T--)
	{
		while(!num.empty())num.pop();
		cin>>aa>>bb;
		num.push(aa);
		int ans=0;
		memset(step,0,sizeof(step));
		bool is_find=false;
		step[aa]=1;
		while(!num.empty())
		{
			if(num.front()==bb){ is_find=true;ans=step[bb]-1;break;}
			aa=num.front();
			num.pop();
			for(int i=1;i<=9;i+=2)
			{
				int t=aa/10*10+i;
				if(t!=aa && !step[t] && a[t]==0)
				{
					num.push(t);
					step[t]=step[aa]+1;				
				}
			}

			for(int i=0;i<=9;++i)
			{
				int l=aa%10;
				int t=aa/10;
				t=t/10*10+i;
				t=t*10+l;
				if(t!=aa && !step[t] && a[t]==0)
				{
					num.push(t);
					step[t]=step[aa]+1;
				}
			}
			for(int i=0;i<=9;++i)
			{
				int l=aa%10+(aa/10) %10 *10;
				int t=aa/100;
				t=t/10*10+i;
				t=t*100+l;
				if(t!=aa && !step[t] && a[t]==0)
				{
					num.push(t);
					step[t]=step[aa]+1;
				}
			}
			for(int i=1;i<=9;++i)
			{
				int l=aa%10+(aa/10)%10*10+(aa/100)%10*100;
				int t=i*1000+l;
				if(t!=aa &&!step[t] && a[t]==0)
				{
					num.push(t);
					step[t]=step[aa]+1;
				}
			}
		}
		if(!is_find)cout<<"Impossible"<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}