include<iostream>

include<cstring>

using namespace std;
class number
{public:
long long p; long long s;
};
long long biao[10000];
bool biaoo(long long a)
{
if (a == 2 || a == 3)
{
return 1;
}
if (a % 2 == 0)
return 0;
for (int i = 2; i*i <= a; i++)
{
if (a%i == 0)return 0;
}
return 1;
}
bool visit[20000];
number queue[20000];
long long bfs(long long a, long long b)
{
memset(visit, 0, sizeof(visit));
long long tou=0, wei=0;
queue[0].p = a;
queue[0].s = 0;
visit[a] = 1;
wei++;
while (tou < wei)
{
number tis = queue[tou];
tou++;//可以放在最后面；
if (tis.p == b)
{
return tis.s;
}
for (long long i = -(tis.p % 10); tis.p % 10 + i >= 0 && tis.p % 10 + i <= 9; i++)
{
long long x = tis.p + i;
if (x != tis.p && visit[x] == 0 && biao[x] == 1)
{
visit[x] = 1;
queue[wei].p = x;
queue[wei].s = tis.s+ 1; wei++;

        }
    }
    for (long long i = -((tis.p/10) % 10); (tis.p / 10) % 10 + i >= 0 && (tis.p / 10) % 10 + i <= 9; i++)
    {
        long long x = tis.p + i*10;
        if (x != tis.p && visit[x] == 0 && biao[x] == 1)
        {
            visit[x] = 1;
            queue[wei].p = x;
            queue[wei].s = tis.s + 1; wei++;

        }
    }
    for (long long i = -((tis.p/100) % 10); (tis.p / 100) % 10 + i >= 0 && (tis.p / 100) % 10 + i <= 9; i++)
    {
        long long x = tis.p + i*100;
        if (x != tis.p && visit[x] == 0 && biao[x] == 1)
        {
            visit[x] = 1;
            queue[wei].p = x;
            queue[wei].s = tis.s + 1; wei++;

        }
    }
    for (long long i = -((tis.p/1000))+1; (tis.p / 1000) + i > 0 && (tis.p / 1000)  + i <= 9; i++)
    {
        long long x = tis.p + i*1000;
        if (x != tis.p && visit[x] == 0 && biao[x] == 1)
        {
            visit[x] = 1;
            queue[wei].p = x;
            queue[wei].s = tis.s + 1; wei++;
        }
    }
    
}
return -1;

}

int main()
{
for (int i = 1000; i <= 10000; i++)
{
biao[i]= biaoo(i);
}
long long n,a,b;
cin >> n;
while (n--)
{
cin >> a >> b;
if (bfs(a, b) == -1)
cout << "Impossible" << endl;
else
cout << bfs(a, b)<<endl;

}

}