#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
int T,n,m,p[10005],vis[10005],ans=2e9;
struct number{
	int num,step;
}st;
queue<number>Q;
bool prime(int x)
{
	for(int i=1;i<=n*n;i++)
		if(x%i==0) return 0;
	return 1;
}
void init()
{
	while(!Q.empty()) Q.pop();
}
int bfs()
{
	Q.push(st);
	while(!Q.empty())
	{
		number now=Q.front();
		if(now.num==m)
		{
			ans=min(ans,now.step);
			return 1;
		}
		Q.pop();
		int a=now.num/1000;
		int b=now.num/100%10;
		int c=now.num/10%10;
		int d=now.num%10;
		for(int i=1;i<10;i++)
		{
			number s;
			s.num=1000*i+100*b+10*c+d;
			s.step=now.step+1;
			if(p[s.num]==1&&!vis[s.num]) Q.push(s);
		}
		for(int i=0;i<10;i++)
		{
			number s;
			s.num=1000*a+100*i+10*c+d;
			s.step=now.step+1;
			if(p[s.num]==1&&!vis[s.num]) Q.push(s);
		}
		for(int i=0;i<10;i++)
		{
			number s;
			s.num=1000*a+100*b+10*i+d;
			s.step=now.step+1;
			if(p[s.num]==1&&!vis[s.num]) Q.push(s);
		}
		for(int i=0;i<10;i++)
		{
			number s;
			s.num=1000*a+100*b+10*c+i;
			s.step=now.step+1;
			if(p[s.num]==1&&!vis[s.num]) Q.push(s);
		}
	}
	return 0;
}
int main()
{
	for(int i=1000;i<=9999;i++) p[i]=prime(i);
	cin>>T;
	while(T--)
	{
		init();
		cin>>n>>m;
		if(n==m)
		{
			cout<<0;
			continue;
		}
		st.num=n,st.step=0;
		if(!bfs()) cout<<"Impossible"<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}