#include<stdio.h>
#include<math.h>
#include<string.h>
#include<malloc.h>

#define N 1070
typedef struct Elemtype{
	int i;
	int len;//store the steps
}Elemtype;

typedef struct Queue{
	Elemtype * base;
	int front,rear;
}Queue;

int prime[N],adj[N][N],visited[N],length;

int One_dif(int m,int n);
int IsPrime(int n);
int locate(int t,int n);
void bfs(int s,int t,int n);
int InitQueue(Queue &Q);
int EnQueue(Queue &Q,Elemtype cur);
int DeQueue(Queue &Q,Elemtype &cur);
int QueueEmpty(Queue Q);

int main()
{

	int n;
	int i,j=0;
	for(i=1001;i<9999;i+=2)// find all prime
	{
		if(IsPrime(i))
			prime[j++]=i;
	}
	n=j;// the total number of the prime
	for(i=0;i<n;i++)// create the graph
	{
		adj[i][i]=0;
		for(j=i+1;j<n;j++)
			if(One_dif(prime[i],prime[j]))
				adj[i][j]=adj[j][i]=1;
	}
	int testcase;
	scanf("%d",&testcase);
	while(testcase--)//process each testcase
	{
		int s,t,si,ti;
		scanf("%d%d",&s,&t);
		si=locate(s,n);// get the location of s in prime[N]
		ti=locate(t,n);
		length=0;
		memset(visited,0,sizeof(visited));//set the array 0
		bfs(si,ti,n);
		if(length==-1)
			printf("Impossible\n");
		else
			printf("%d\n",length);
	} 
	return 0;
}

int IsPrime(int n)
{
	int i,k;
	k=(int)sqrt((long double)n);
	for(i=2;i<=k;i++)
		if(n%i==0)
			return 0;
	return 1;
}
	
int One_dif(int m,int n)
{
	int same=0,t=4;
	while(t--)
	{
		if(m%10==n%10)
			same++;
		m=m/10;
		n=n/10;
	}
	if(same==3)
		return 1;
	else
		return 0;
}

int locate(int t,int n)
{
	int i;
	for(i=0;i<n;i++)
		if(prime[i]==t)
			return i;

	return -1;
}
void bfs(int s,int t,int n)
{
	int i;
	Queue Q;
	Elemtype S,cur;
	S.i=s;
	S.len=0;
	InitQueue(Q);
	EnQueue(Q,S);
	while(!QueueEmpty(Q))
	{
		DeQueue(Q,cur);
		if(cur.i==t)
		{
			length=cur.len;
			return ;
		}
		visited[cur.i]=1;
		length=cur.len+1;
		for(i=0;i<n;i++)
			if(adj[cur.i][i]==1 && !visited[i])
			{
				Elemtype Cur;
				Cur.i=i;
				Cur.len=length;// get the steps
				EnQueue(Q,Cur);
			}
	}
	length=-1;
	return;
}
		
int InitQueue(Queue &Q)
{
    Q.base=(Elemtype *)malloc(sizeof(Elemtype)*N);
    Q.front=Q.rear=0;
    return 0;
}

int EnQueue(Queue &Q,Elemtype cur)
{
    if((Q.rear+1)%N==Q.front)
        return 0;
    Q.base[Q.rear].i=cur.i;
	Q.base[Q.rear].len=cur.len;
    Q.rear=(1+Q.rear)%N;
    return 1;
}

int DeQueue(Queue &Q,Elemtype &cur)
{
    if(Q.rear==Q.front)
        return 0;
    cur.i=Q.base[Q.front].i;
	cur.len=Q.base[Q.front].len;
    Q.front=(Q.front+1)%N;
    return 1;
}

int QueueEmpty(Queue Q)
{
    if(Q.rear==Q.front)
        return 1;
    else
         return 0;
}