/*

     题意：从一个数到另外一个数，每次改变一个数字，且每次是素数

     BFS：先预处理1000到9999的素数，简单BFS一下。我没输出Impossible都AC，数据有点弱

 */

 /************************************************

 Author        :Running_Time

 Created Time  :2015-8-2 15:46:57

 File Name     :POJ_3126.cpp

 *************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef long long ll;

 const int MAXN = 1e4 + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 bool is_prime[MAXN];

 bool vis[MAXN];

 int x, y, res;

 struct Digit    {

     int d[];

     int step;

 };

 void solve(void)    {

     memset (is_prime, true, sizeof (is_prime));

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

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

             if (i % j == ) {

                 is_prime[i] = false;    break;

             }

         }

     }

 }

 int get_num(int *a) {

     int ret = ;

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

         ret = ret *  + a[i];

     }

     return ret;

 }

 void BFS(int u, int v)   {

     Digit tmp;

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

         tmp.d[i] = u % ;  u /= ;

     }

     tmp.step = ;

     queue<Digit> Q; Q.push (tmp);   vis[u] = true;

     int ans = -;

     while (!Q.empty ()) {

         Digit x = Q.front ();   Q.pop ();

         int m = get_num (x.d);

         if (m == v) {

             ans = x.step;   break;

         }

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

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

                 if (i ==  && j == )   continue;

                 if (x.d[i] != j)    {

                     Digit y = x;

                     y.d[i] = j; m = get_num (y.d);

                     if (is_prime[m] && !vis[m])    {

                         vis[m] = true;  y.step++;   Q.push (y);

                     }

                 }

             }

         }

     }

     if (ans == -)  puts ("Impossible");

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

 }

 int main(void)    {       //POJ 3126 Prime Path

     solve ();

     int T;  scanf ("%d", &T);

     while (T--) {

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

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

         BFS (x, y);

     }

     return ;

 }