#include<bits/stdc++.h>
using namespace std;
int get(int x) // k的因数中除k以外最大的因数。
{
    for(int i=2;i<=sqrt(x);i++)
    {
        if(x%i==0) return x/i;
    }
    return 1;
}
int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        int res=0;
        while(x!=y)
        {
            if(x>y) x=get(x); //x往上走
            else y=get(y); 
            res++;
        }
        cout<<res<<endl;
    }
    return 0;
}