原题：https://www.acwing.com/problem/content/description/4223/
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=10010;
int st[N];
int prime[N],cnt;
int dist[N];
void init(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]){
st[i]=true;
prime[cnt++]=i;
}
for(int j=0;i<=n/prime[j];j++)
{
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}
bool check(int a,int b)
{
int diff=0;
for(int i=0;i<4;i++)
{
if(a%10!=b%10){
diff++;
}
a/=10,b/=10;
}
if(diff==1) return true;
return false;
}
bool bfs(int a,int b)
{
queue<int> q;
q.push(a);
memset(st,0,sizeof st);
memset(dist,0x3f,sizeof dist);
dist[a]=0;
while(q.size()){
int t=q.front();
//cout<<t<<endl;
q.pop();
if(t==b) return true;
for(int i=0;i<cnt;i++)
{
if(prime[i]<1000||prime[i]>=10000) continue;
if(st[prime[i]]) continue;
if(!check(prime[i],t)) continue;
if(dist[prime[i]]>dist[t]+1)
{
dist[prime[i]]=dist[t]+1;
st[prime[i]]=true;
q.push(prime[i]);
}
}
}
return false;
}
int main()
{
init(N-1);
int T;
cin>>T;
while(T--)
{
int a,b;
cin>>a>>b;
if(bfs(a,b)){
cout<<dist[b]<<endl;
}
else puts("Impossible");
}
return 0;
}