#include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<stack>

 #include<queue>

 #include<iomanip>

 #include<cmath>

 #include<map>

 #include<vector>

 #include<algorithm>

 using namespace std;

 int p[],vis[];

 int a,b,t;

 struct node

 {

     int a,step;

 }pos,next;

 void prime() //快速求素数的模板

 {

     int i,j;

     memset(p,-,sizeof(p));

     p[]=p[]=;

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

     {

         if(i%==) p[i]=;

         if(p[i])

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

         p[j]=;

     }

 }

 int change(int x,int i,int j) //i代表改变哪一位（个十百千），j代表改变为几，x是原数

 {

     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 ;

 }

 void bfs()

 {

     int i,j;

     queue<node>q;

     next.a=a; next.step=;

     vis[a]=;

     q.push(next);

     while(!q.empty())

     {

         pos=q.front();

         q.pop();

         next.step=pos.step+;

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

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

         {

             if(i==&&j==)

             continue;

             next.a=change(pos.a,i,j);

             if(next.a==b)

             {

                 cout<<next.step<<endl;

                 return;

             }

             if(p[next.a]&&!vis[next.a])

             {

                 q.push(next); vis[next.a]=;

             }

         }

     }

     cout<<"Impossible"<<endl;

 }

 int main()

 {

     prime();

     cin>>t;

     while(t--)

     {

         memset(vis,,sizeof(vis));

         cin>>a>>b;

         if(a==b)

         {

             cout<<""<<endl;

             continue;

         }

         bfs();

     }

     return ;

 }