#include <iostream>

#include <cstdio>

#include <queue>

#include <cmath>

#include <map>

using namespace std;

struct Struct

{

    int num;

    int step;

};

bool Prime(int a) //判断是否为质数

{

    for(int i=2;i<=sqrt(a);i++)

        if(a%i==0)

            return false;

    return true;

}

int bfs(int a,int b)

{

    queue<Struct>q;

    map<int,bool>m; //用map来标记数字是否被访问过

    Struct temp,next;

    temp.num=a;

    temp.step=0;

    m[a]=true;

    q.push(temp);

    while(!q.empty())

    {

        temp=q.front();

        if(temp.num==b)

            return temp.step;

        q.pop();

        for(int i=1;i<10;i++) //变换千位

        {

            next=temp;

            next.num=next.num%1000+i*1000;

            if(!m[next.num] && Prime(next.num))

            {

                m[next.num]=true;

                next.step++;

                q.push(next);

            }

        }

        int x=100;

        for(int i=0;i<3;i++) //变换百位，十位，个位

        {

            for(int j=0;j<10;j++)

            {

                next=temp;

                next.num=next.num%x+j*x+next.num/(x*10)*(x*10);

                if(!m[next.num] && Prime(next.num))

                {

                    m[next.num]=true;

                    next.step++;

                    q.push(next);

                }

            }

            x=x/10;

        }

    }

    return -1;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n;

    scanf("%d",&n);

    while(n--)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        int ans=bfs(a,b);

        if(ans!=-1)

            printf("%d\n",ans);

        else

            printf("Impossible\n");

    }

    return 0;

}