#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cmath>

#include<map>

#include<queue>

#include<stdlib.h>

#include<string>

using namespace std;

typedef long long LL;

const int maxn=;

const int INF=0x3f3f3f3f;

int t,s;

int a[maxn];

bool vis[maxn];

bool fun(int x)

{

    for(int i=; i*i<=x; ++i)

        if(x%i==)return ;

    return ;

}

struct Data

{

    int b[];

} d,e;

queue<Data>q;

int get(Data x)

{

    int ans=;

    for(int i=; i>=; --i)

        ans=ans*+x.b[i];

    return ans;

}

int main()

{

    int T;

    for(int i=; i<; ++i)

        if(fun(i))vis[i]=;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&s,&t);

        memset(a,-,sizeof(a));

        while(!q.empty())q.pop();

        if(!vis[s]||!vis[t])

        {

            printf("Impossible\n");

            continue;

        }

        a[s]=;

        for(int i=; i<; ++i)

        {

            d.b[i]=s%;

            s/=;

        }

        q.push(d);

        while(!q.empty())

        {

            e=d=q.front();

            q.pop();

            int k=get(d);

            if(k==t)break;

            for(int i=; i<; ++i)

            {

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

                {

                    if(j==d.b[i])continue;

                    e.b[i]=j;

                    int x=get(e);

                    if(!vis[x]||a[x]>=)continue;

                    a[x]=a[k]+;

                    q.push(e);

                }

                e.b[i]=d.b[i];

            }

        }

        if(a[t]==-)

        {

              printf("Impossible\n");

              continue;

        }

        printf("%d\n",a[t]);

    }

    return ;

}