#include<bits/stdc++.h>
#define LL long long
#define N ((int)6e4 + 5)
#define MOD ((int)998244353 + 0)
#define MAX ((int)1e9 + 7)
#define MAXL ((ll)1e18 + 7)
#define MAXP ((int)1e3 + 7)
#define thr 1e-8
#define pi acos(-1)  /// pi = acos ( -1 )
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define endl "\n"

using namespace std;



vector < int > edg[1005]; /// edg[0] , edg[1] , edg[2]

/// edg[i] = nodes connected to node 'i'

void AddEdge(int u , int v)
{
    edg[u].push_back(v);
}



void bfs(int source){
    queue < int > que;
    que.push(source);
    memset(dis,-1,sizeof dis);
    dis[source] = 0;
    while(!que.empty()){
        int node = que.front();
        que.pop();
        for(int u:edg[node]){
            if(vis[u] == 0){
                que.push(u);
                dis[u] = dep[node] + 1;
            }
        }
    }
}




void BuildGraph()
{
    vector < int > prime = Sieve(1000);
    for(int i = 4 ; i <= 1000 ; i++){
        for(int p:prime){
            if(p < i && i % p == 0){
                AddEdge(i , i + p);
            }
        }
    }
}



int main()
{

    /// problem: https://lightoj.com/problem/number-transformation
    int t;
    cin>>t;

    BuildGraph();

    while(t--){
        int source , des;
        cin>>source >> des;
        bfs(source); /// O(n + m)
        cout<<dis[des]<<endl;
    }

    /// O(n*n + t*(n+m));


    return 0;
}