#include<bits/stdc++.h>
#define MAX 10000
#define pb push_back
 
using namespace std;
 
bool check[MAX];
 
char store[5],store1[5];
 
vector<int>graph[MAX],prime;
 
bool color[MAX];
 
int cost[MAX];
 
void sieve()
{
    int i,j,k;
 
    k = sqrt(MAX);
 
    for(i=3; i<=k; i+=2)
    {
        for(j=i*i; j<=MAX; j+=2*i)
        {
            check[j] = true;
        }
    }
 
    for(i=4; i<=MAX; i+=2)
    {
        check[i] = true;
    }
 
    for(i=1001; i<=9999; i+=2)
    {
        if(!check[i])
        {
            prime.pb(i);
        }
    }
}
 
void make_graph()
{
    int len = prime.size();
 
    int i,j,k;
 
    for(i=0; i<len; i++)
    {
        for(j=i+1; j<len; j++)
        {
            sprintf(store,"%d",prime[i]);
 
            sprintf(store1,"%d",prime[j]);
 
            int cnt = 0;
 
            for(k=0; k<4; k++)
            {
                if(store[k]==store1[k])
                {
                    cnt++;
                }
            }
 
            if(cnt==3)
            {
                graph[prime[i]].pb(prime[j]);
 
                graph[prime[j]].pb(prime[i]);
            }
        }
    }
}
 
void BFS(int source)
{
    memset(color,0,sizeof(color));
 
    memset(cost,0,sizeof(cost));
 
    queue<int>Q;
 
    int u,v,i,len;
 
    color[source] = true;
 
    cost[source] = 0;
 
    Q.push(source);
 
    while(!Q.empty())
    {
        u = Q.front();
 
        Q.pop();
 
        len = graph[u].size();
 
        for(i=0; i<len; i++)
        {
            v = graph[u][i];
 
            if(color[v]==false)
            {
                color[v] = true;
 
                cost[v] = cost[u]+1;
 
                Q.push(v);
            }
        }
    }
}
 
int main()
{
    sieve();
 
    make_graph();
 
    int test,src,dest;
 
    scanf("%d",&test);
 
    while(test--)
    {
        scanf("%d%d",&src,&dest);
 
        if(src==dest)
        {
            puts("0");
 
            continue;
        }
 
        BFS(src);
 
        if(cost[dest])
        {
            printf("%d\n",cost[dest]);
        }
        else
        {
            puts("Impossible");
        }
    }
 
    return 0;
}