#include<bits/stdc++.h>

 using namespace std;

 bool isPrime(int n){//素数判断

     if(n ==  || n == ) return true;

     else{

         int k = sqrt(n) + ;

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

             if(n % i == ) return false;

         }

         return true;

     }

 }

 bool Prime[];

 int visit[];

 void getPrime(){

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

         if(isPrime(i))Prime[i] = true;

     }

 }

 struct Node{

     int num;//储存数字

     int cost;//操作步数

 }; 

 Node bfs(int start, int end){

     queue<Node> q;

     Node front;

     front.num = start;

     front.cost = ;

     visit[start] = ;

     q.push(front);

     while(!q.empty()){

         front = q.front(); q.pop();

         for(int i = ; i < ; i++){//换千位

             int m = front.num;

             m = m %  + i * ;

             if(!visit[m] && Prime[m]){

                 visit[m] = ;

                 Node tmp = front;

                 tmp.num = m;

                 tmp.cost++;

                 q.push(tmp);

                 if(m == end)return tmp;

             }

         }

         for(int i = ; i < ; i++){//换百位

             int m = front.num;

             m = m %  + (m/) *  + i * ;

             if(!visit[m] && Prime[m]){

                 visit[m] = ;

                 Node tmp = front;

                 tmp.num = m;

                 tmp.cost++;

                 q.push(tmp);

                 if(m == end)return tmp;

             }

         }

         for(int i = ; i < ; i++){//换十位

             int m = front.num;

             m = m %  + (m/) *  + i * ;

             if(!visit[m] && Prime[m]){

                 visit[m] = ;

                 Node tmp = front;

                 tmp.num = m;

                 tmp.cost++;

                 q.push(tmp);

                 if(m == end)return tmp;

             }

         }

         for(int i = ; i < ; i++){//换个位

             int m = front.num;

             m = (m/) *  + i;

             if(!visit[m] && Prime[m]){

                 visit[m] = ;

                 Node tmp = front;

                 tmp.num = m;

                 tmp.cost++;

                 q.push(tmp);

                 if(m == end)return tmp;

             }

         }

     }

     Node tmp;

     tmp.num = ;

     tmp.cost = ;

     return tmp;

 }

 int main(){

     int n;

     cin >> n;

     getPrime();

     while(n--){

         int a, b;

         cin >> a >> b;

         Node tmp;

         memset(visit, , sizeof(visit));

         tmp = bfs(a, b);

         if(tmp.num ==  && tmp.cost == ) cout <<  << endl;

         else{

             cout << tmp.cost << endl;

         }

     }

 }