Untitled

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using ll = long long;
using ld = long double;
using db = double;
using namespace std;
using namespace __gnu_pbds;
const ll M = 1e9+7, M2 = 1e9+9;
const int N = 1e5 + 7;
const double eps = 1e-9, pi = acos(-1);
const ll OO = 1e18;
int dx[]{0, 1, 0, -1, 1, 1, -1, -1};
int dy[]{1, 0, -1, 0, 1, -1, -1, 1};
char di[]{'R', 'D', 'U', 'L'};
template<typename T> using ordered_set = tree<
        T,
        null_type,
        std::less<T>,
        rb_tree_tag,
        tree_order_statistics_node_update>;


/*
* success is my only option - failure is not
*/
using ull = unsigned long long;
ull modmul(ull a, ull b, ull m)
{
    ll ret = a * b - m * ull(1.L / m * a * b);
    return ret + m * (ret < 0) - m * (ret >= (ll) m);
}
ull modpow(ull b, ull e, ull m)
{
    ull ans = 1;
    for (; e; b = modmul(b, b, m), e /= 2)
        if (e & 1) ans = modmul(ans, b, m);
    return ans;
}
bool isprime(ull n)
{
    if (n < 2 || n % 6 % 4 != 1)
        return (n | 1) == 3;
    ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
    s = __builtin_ctzll(n - 1), d = n >> s;
    for (ull a : A)
    {
        ull p = modpow(a%n, d, n), i = s;
        while (p != 1 && p != n -1 && a % n && i--)
            p = modmul(p, p, n);
        if (p != n - 1 && i != s)
            return false;
    }
    return true;
}
ull polard(ull n)
{
    auto f = [n](ull x) {return modmul(x, x, n) + 1;};
    ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
    while (t++ % 40 || __gcd(prd, n) == 1)
    {
        if (x == y)
            x = ++i, y = f(x);
        if ((q = modmul(prd, max(x, y) - min(x, y), n)))
            prd = q;
        x = f(x), y = f(f(y));
    }
    return (__gcd(prd, n));
}
vector<ull>factor(ull n)
{
    if (n == 1)
        return {};
    if (isprime(n)) return {n};
    ull x = polard(n);
    auto l = factor(x), r= factor(n / x);
    l.insert(l.end(), r.begin(), r.end());
    return l;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
#endif
    ll tt; cin >> tt; for (int ttt = 1; ttt <= tt; ++ttt)
    {
        ll a, b;
        map<ull, ll>frq, frq2;

        cin >> a >> b;
        auto x = factor(a);
        auto y = factor(b);
        auto tmp = x;
        tmp.insert(tmp.end(), y.begin(), y.end());
        for (auto i : tmp)
            frq[i]++;
        bool f=  0;
        for (auto [x, y] : frq)
            f |= (y & 1);
        if (f)
        {
            cout << -1 << '\n';
            continue;
        }
        for (auto i : x)
            frq2[i]++;
        ll ans = 0;
        for (auto [i, j] : frq)
        {
            ans += abs(j / 2 - frq2[i]);
        }
        cout << ans;
        cout << "\n";
    }
    return 0;
}