#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std ;

const int maxn =  ;

const int maxm =  ;

struct node

{

    int k,step ;//当前素数为k,路径长度为step

} h[maxn] ;

int p[maxn] ;

int x,y,n,s[maxn] ;

void prim()

{

    memset(p,,sizeof(p));

    p[] = p[] =  ;

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

    {

        if(!p[i])

        {

            for(int j = i*i ; j <= maxm ; j += i)

            {

                p[j] =  ;

            }

        }

    }

}

int change(int x,int i,int j)//x的第i位数改为j

{

    if(i == ) return(x/)*+j ;//个位数

    else if(i == ) return (x/)*+x%+j* ;

    else if(i == ) return (x/)*+x%+j* ;

    else if(i == ) return (x%)+j* ;

    return  ;

}

int main()

{

    prim() ;//生成[2....9999]之间的素数

    cin>>n;//输入测试用例数

    while(n--)

    {

        cin>>x>>y ;//输入初始素数和目标素数

        h[].k = x ; //宽度优先搜索，初始素数进入队列

        h[].step =  ;

        int l =  ,r =  ;//队列首尾指针初始化

        memset(s,,sizeof(s)) ;//所有素数的路径长度初始化

        int ans = - ;//最小花费初始化

        while()

        {

            if(h[l].k == y)//若达到目标素数，则记下路径长度并退出循环

            {

                ans = h[l].step ;

                break ;

            }

            int tk,ts ;

            for(int i =  ; i <=  ; i++)//依次改变队首节点的每一位

            {

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

                {

                    if(!((j == )&&(i == )))//依次枚举第i位的改变值(不允许最高位变为0)

                    {

                        tk = change(h[l].k,i,j);//计算队首节点的第i位变为j的数tk

                        if(p[tk])//若tk为合数，继续枚举

                            continue;

                        ts = h[l].step+ ;//计算得到的素数tk的路径长度

                        if(ts >= s[tk])

                            continue ;//若路径长度非最短，则继续枚举

                        if(tk == y)//若tk为目标素数，则记下路径长度并推出循环

                        {

                            ans = ts;

                            break ;

                        }

                        s[tk] = ts;//记下到素数tk的路径长度

                        r++ ;

                        h[r].k = tk ;//素数tk及其路径长度入队列

                        h[r].step = ts ;

                    }

                }

            }

            if(l == r||ans >= )//若队列空或者得到的目标素数，则退出循环

                break ;

            l++ ;//队首指针+1；

        }

        if(ans >= )//若得到目标素数，则输出最短路径

            cout<<ans<<endl ;

        else

            cout<<"Impossible"<<endl ;

    }

    return  ;

}