#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=10000,maxg=1500,oo=19930128;
int t,a,b,start,end,n,list[maxn],* list1;
bool shai[maxn+10];
struct node{
  int w,v;
};
vector<node> elist[maxn];
void clear(int x)
{
  for(int i=2;i*x<=maxn;++i)
	shai[i*x]=true;
}
bool check(int x)
{
  int t=(int)(sqrt((double)x)+1);
  for(int i=1;i<=n;++i){
	if(x%list[i]==0)return false;
	if(list[i]>t)break;
  }
  return true;
}
void makelist()
{
  n=0;
  for(int i=2;i<=maxn;++i){
	if(shai[i])continue;
	else 
	  if(check(i)){
		clear(i);
		list[++n]=i;
	  }
	  else{
		shai[i]=true;
		clear(i);
	  }
  }
  for(int i=1;i<=n;++i)
	if(list[i]>1000){
	  list1=&list[i-1];
	  n=n-i+1;
	  break;
	}	
}
int dis(int x,int y)
{
  int s=0;
  while(x>0&&y>0){
	s+=((x%10==y%10)?0:1);
	x/=10;
	y/=10;
  }
  return s;
}
void makegraph()
{
  for(int i=1;i<=n;++i)
	for(int j=i+1;j<=n;++j){
	  if( dis( list1[i],list1[j] )==1){
		node tmp;
		tmp.w=1;
		tmp.v=j;elist[i].push_back(tmp);
		tmp.v=i;elist[j].push_back(tmp);
	  }
	}
}
void datain()
{
  scanf("%d%d",&a,&b);
}
int d[maxg];
bool relax(int u,int v,int w)
{
  if(d[u]+w<d[v]){
	d[v]=d[u]+w;
	return true;
  }
  return false;
}
bool spfa(int v0)
{
  bool vis[maxg];
  int h[maxg],que[maxg],head=0,tail=1;
  memset(vis,0,sizeof(vis));
  vis[v0]=true;
  h[v0]=1;
  que[1]=v0;
  for(int i=1;i<=n;++i)
	d[i]=oo;
  d[v0]=0;
  while(head!=tail){
	if(++head>n)head=1;
	int vi=que[head];
	for(vector<node>::iterator p = elist[vi].begin();
		p!=elist[vi].end();++p){
	  if(relax(vi,p->v,p->w))
		if(!vis[p->v]){
		  if(++tail>n)tail=1;
		  que[tail]=p->v;
		  vis[p->v]=true;
		  if(++h[p->v]>n)return false;
		}
	}
	vis[vi]=false;
  }
  return true;
}
void work()
{
  for(int i=1;i<=n;++i){
	if(list1[i]==a)start=i;
	if(list1[i]==b)end=i;
  }
  spfa(start);
  if(d[end]<oo)printf("%d\n",d[end]);
  else printf("Impossible\n");
}
int main()
{
#ifndef ONLINE_JUDGE
  freopen("p3126.in","r",stdin);
  //freopen(".out","w",stdout); 
#endif
  makelist();
  makegraph();
  scanf("%d",&t);
  for(int i=1;i<=t;++i){
	datain();
	work();
  }
  return 0;
}