#include <iostream>
using namespace std;
#pragma warning(disable:4996)
#define maxsize 1000
#define inf 1 << 20
#define number_of_Primes 1060
#pragma optimize( "apt", on )
int plist[10005], pcount = 0;
typedef struct point { int prime, id, next_prime, weight; } P;
bool visit[10000];
P v[10000];
struct que{ P info; int cishu; }q[10000];
int prime(int n)
{
int i;
if ((n != 2 && !(n % 2)) || (n != 3 && !(n % 3)) || (n != 5 && !(n % 5)) || (n != 7 && !(n % 7)))
return 0;
for (i = 0; plist[i] * plist[i] <= n; i++)
if (!(n%plist[i]))
return 0;
return n>1;
}
void initprime()
{
int i;
for (plist[pcount++] = 2, i = 3; i<50000; i++)
if (prime(i))
plist[pcount++] = i;
}
bool judge(int a, int b)
{
char s1[5], s2[5];
_itoa_s(a, s1, 10);
_itoa_s(b, s2, 10);
int countt = 0;
for (int i = 0; i < 4; i++)
{
if (s1[i] != s2[i])
{
countt++;
}
}
if (countt == 1) return true;
return false;
}
int buildgraph()
{
//168-1228
/*point start;
start = { prime_start, 1, 0, 0 };
visit[prime_start] = true;
v.push_back(start);*/
int countt = 1;
int cnt = 0;
for (int i = 168; i <= 1228; i++)//from no.168 in plist[], to no.1228
{
for (int j = 168; j <= 1228; j++)
{
if (judge(plist[i], plist[j]))
{
point temp;
temp.prime = plist[i];
temp.id = countt++;
temp.next_prime = plist[j];
temp.weight = 1;
v[cnt++] = temp;
}
}
}
return cnt;//size of sets...
}
int Bin_search(P *v, int size, int prime)
{
int mid = size >> 1;
int min = 0, max = size;
while (min <= max)
{
mid = (min + max) >> 1;
if (v[mid].prime == prime && v[mid - 1].prime == prime && v[mid + 1].prime != prime)
{//return the first one(with same "prime" but not same id) in v[]
while (v[mid].prime == prime)
--mid;
return ++mid;
}
else if (v[mid].prime > prime) max = mid - 1;
else min = mid + 1;
}
}
int bfs(P *v, int size, int prime_start, int prime_end)
{
memset(visit, false, sizeof(visit));
if (prime_start == prime_end) { return 0; }
int i = Bin_search(v, size, prime_start);
//cout << v[i].prime << ' ' << v[i].id << endl;
/*for (int i = 0; i < size; i++)
{
cout << v[i].prime << ' ' << v[i].id << ' ' << v[i].next_prime << ' ' << endl;
}*/
visit[v[i].prime] = true;
int tail = 0, head = 0;
for (; v[i].prime == v[i + 1].prime; i++)//push anyone whose "prime" equals to prime_start
{//but the last one is left over
q[tail].info = v[i];
q[tail++].cishu = 1;
visit[v[i].next_prime] = true;
}
//push the last one whose "prime" equals to prime_start
q[tail].info = v[i];
q[tail++].cishu = 1;
visit[v[i].next_prime] = true;
while (tail != head)//while the queue is not empty
{
que temp = q[head];
//cout << temp.cishu << endl;
head++;
if (temp.info.next_prime == prime_end) return temp.cishu;
int pos = Bin_search(v, size, temp.info.next_prime);
for (; v[pos].prime == v[pos + 1].prime ; pos++)
{
if (visit[v[pos].next_prime] == false)
{
q[tail].info = v[pos];
q[tail++].cishu = temp.cishu + 1;
visit[v[pos].next_prime] = true;
}
}
if (visit[v[pos].next_prime] == false)
{
q[tail].info = v[pos];
q[tail++].cishu = temp.cishu + 1;
visit[v[pos].next_prime] = true;
}
}
return -1;//found nothing
}
int main()
{
int n;
initprime();
int size = buildgraph();
cin >> n;
while (n--)
{
int s, e;
scanf("%d%d", &s, &e);
printf("%d\n", bfs(v, size, s, e));
}
}