#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = 10000;

bool p[maxn];
int ans[maxn];
int b[9 * 4], num;

void calPrime()
{
    p[2] = true;
    for(int i = 3; i < maxn; i += 2)p[i] = true;
    for(int i = 3; i < maxn; i += 2)
    {
        if(p[i])
        {
            for(int j = 3; j * i < maxn; j+= 2)
            {
                p[i * j] = false;
            }
        }
    }
}

void getSameShape(int s)
{
    num = 0;
    for(int base = 1; base < maxn; base *= 10)
    {
        int t = s - ((s % (base * 10)) / base) * base;
        for(int i = 0; i < 10; i++)
        {
            int tmp = t + i * base;
            if(tmp > 1000 && p[tmp] && tmp != s)
            {
                b[num++] = tmp;
            }
        }
    }
}

void calAns(int s, int e)
{
    memset(ans, -1, sizeof ans);
    if(!p[s])return;
    ans[s] = 0;
    queue<int> que;
    que.push(s);
    while(!que.empty())
    {
        s = que.front();
        que.pop();
        getSameShape(s);
        for(int j = 0; j < num; j++)
        {
            if(ans[b[j]] == -1)
            {
                ans[b[j]] = ans[s] + 1;
                if(e == b[j])return;
                que.push(b[j]);
            }
        }

    }
}

int main()
{
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif // LOCAL
    int n, m;
    int T;
    calPrime();
    scanf("%d",&T);
    for(int ti = 0; ti < T && scanf("%d%d", &n, &m) == 2; ti++)
    {
        calAns(n, m);
        if(ans[m] != -1)printf("%d\n",ans[m]);
        else puts("Impossible");
    }
    return 0;
}