#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<utility>
using namespace std;
const int MAXN=1e4+1;
typedef pair<int,int> P;
bool is_prime[MAXN];
int prime[MAXN];
bool vis[MAXN];
int p=0;
int arr1[4];//临时存放各位
int arr2[4];//临时存放各位
vector<int>G[MAXN];
bool check(int i,int j)//是否连通
{
    int cnt=0;
    int a=prime[i];
    int b=prime[j];
    while(a)
    {
        arr1[cnt++]=a%10;
        a/=10;
    }
    cnt=0;
    while(b)
    {
        arr2[cnt++]=b%10;
        b/=10;
    }
    cnt=0;
    for(int i=0;i<4;++i)
    {
        if(arr1[i]-arr2[i]!=0)
            cnt++;
    }
    if(cnt>1) return false;
    else return true;
}
void sieve()//素数筛
{
    for(int i=0;i<MAXN;++i)
    {
        is_prime[i]=true;
    }
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<MAXN;++i)
    {
        if(is_prime[i])
        {
            if(i>1000)
                prime[p++]=i;
            for(int j=2*i;j<MAXN;j+=i)
            {
                is_prime[j]=false;
            }
        }
    }
}
void make_graph()//建图
{
    for(int i=0;i<p;++i)
    {
        for(int j=i+1;j<p;++j)
        {
            if(check(i,j))
            {
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
}
int BFS(int x,int y)
{
    int minn=1<<30;
    queue<P>que;
    que.push(P(x,0));
    while(!que.empty())
    {
        P tmp=que.front();
        que.pop();
        int u=tmp.first;
        int s=tmp.second;
        if(u==y)
        {
            minn=min(minn,s);
        }
        for(int i=0;i<G[u].size();++i)
        {
            int v=G[u][i];
            if(!vis[v])
            {
                vis[v]=true;
                que.push(P(v,s+1));
            }
        }
    }
    return minn;
}
int main()
{
    int T;
    scanf("%d",&T);
    sieve();
    make_graph();
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        int st,ed;
        scanf("%d%d",&st,&ed);
        st=lower_bound(prime,prime+p,st)-prime;
        ed=lower_bound(prime,prime+p,ed)-prime;
        if(ed==p)//非素数时
            printf("Impossible\n");
        else
        {
            int ans=BFS(st,ed);
            if(ans==(1<<30))
                printf("Impossible\n");
            else
                printf("%d\n",ans);
        }
    }
    return 0;
}