#include <cstdio>

#include <queue>

#include <cmath>

#include <cstring>

#include <iostream>

using namespace std;

#define M  10000

int prime[M];

bool isprime(int x)   //素数打表

{

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

  if(x%i==) return false;

  return true;

}

void init()

{

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

 {

  if(isprime(i)) prime[i]=;

  else prime[i]=;

  }

}

int bfs(int a,int b)

{

 queue<int>q;

 bool vis[M];

 int cout[M],t[],temp;

 memset(vis,false,sizeof(vis));

 memset(cout,,sizeof(cout));

 q.push(a);//入队

 vis[a]=true;

 while(!q.empty())//判断队列是否为空

 {

  int x=q.front();

  q.pop();

  t[]=x/;

  t[]=x/%;

  t[]=x/%;

  t[]=x%;

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

  {

   int temp=t[j];

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

    if(i!=temp)

    {

     t[j]=i;

     int y=t[]*+t[]*+t[]*+t[];

     if(!vis[y]&&prime[y])

     {

      cout[y]=cout[x]+;

      vis[y]=true;

      q.push(y);

     }

    if(y==b) return cout[y];

    }

   t[j]=temp;

  }

  if(x==b) return cout[x];

 }

 return -;

}

int main()

{

 init();

 int n,x,t,f;

 scanf("%d",&t);

 while(t--)

 {

   scanf("%d %d",&n,&x);

   f=bfs(n,x);

   if(f!=-) printf("%d\n",f);

   else      printf("Impossible\n");

  }

 return ;

}