#include"cstdio"
#include"queue"
#include"cstring"
using namespace std;
const int MAXN=10000;
typedef pair<int,int> P;
int vis[MAXN];
int s,e;
bool prime(int x)
{
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
return false;
}
}
return true;
}
void bfs()
{
queue<P> que;
que.push(P(0,s));
vis[s]=1;
while(!que.empty())
{
P now = que.front();que.pop();
if(now.second==e)
{
printf("%d
",now.first);
return ;
}
int p=now.second%10;
int pp=(now.second%100)/10;
for(int i=1;i<=9;i+=2) //枚举个位
{
int next=(now.second/10)*10+i;
if(!vis[next]&&next!=now.second&&prime(next))
{
vis[next]=1;
que.push(P(now.first+1,next));
}
}
for(int i=0;i<=9;i++) //枚举十位
{
int next=(now.second/100)*100+i*10+p;
if(!vis[next]&&next!=now.second&&prime(next))
{
vis[next]=1;
que.push(P(now.first+1,next));
}
}
for(int i=0;i<=9;i++) //枚举百位
{
int next=(now.second/1000)*1000+i*100+pp*10+p;
if(!vis[next]&&next!=now.second&&prime(next))
{
vis[next]=1;
que.push(P(now.first+1,next));
}
}
for(int i=1;i<=9;i++) //枚举千位
{
int next=i*1000+now.second%1000;
if(!vis[next]&&next!=now.second&&prime(next))
{
vis[next]=1;
que.push(P(now.first+1,next));
}
}
}
printf("Impossible
");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&s,&e);
memset(vis,0,sizeof(vis));
bfs();
}
return 0;
}