模拟

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll solve(ll n)
{
    for(ll i = 2;i<=sqrt(n);i++)
        if(n%i==0)
            return n/i;
    return 1; 
}
ll q;
int main()
{
    cin>>q;
    while(q--)
    {
        ll x,y,ans = 0;cin>>x>>y;
        while(x!=y)
        {
            if(x>y)
                ans++,x = solve(x);
            else if(x<y)
                ans++,y = solve(y);
        }
        cout<<ans<<endl;
    }
    return 0;
}