74

#include <bits/stdc++.h>
using namespace std;


const int N = 1e6;
int fact[N + 1];
vector<int> pr;



int main(){
    //freopen("Test.INP", "r", stdin);
    //freopen("Test.OUT", "w", stdout);
    cin.tie(NULL)->sync_with_stdio(false);


    for (int i = 2; i <= N; ++i) {
        if (fact[i] == 0)
            fact[i] = 1,
            pr.push_back(i);
        for (int j : pr)
            if (j <= i && j*i <= N)
                fact[j*i] = fact[i] + 1;
            else break;
    }


    int q;
    for (cin >> q; q--;) {
        int a, b, t;
        cin >> a >> b;
        t = __gcd(a, b);
        cout << max (fact[a/t], fact[b/t]) << '\n';
    }


    return 0;
}