CF ROUND 1027 F TLE

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

bool check_div(ll x, ll k)
{
    for (ll i = 2; i * i <= x; ++i)
        while (x % i == 0)
            x /= i;
    return x <= k;
}

ll calc_step(ll x, ll k)
{
    vl dist(x + 1, LLONG_MAX / 2);
    dist[1] = 0;
    queue<ll> q;
    q.push(1);
    while (!q.empty()) {
        ll u = q.front(), step = dist[u];
        q.pop();
        for (ll i = 2; i <= k && u * i <= x; ++i) {
            ll v = u * i;
            if (x % v)
                continue;
            if (dist[v] != LLONG_MAX / 2)
                continue;
            dist[v] = step + 1;
            q.push(v);
        }
    }
    dbg(x, k, dist[x]);
    return dist[x];
}

void solve2()
{
    ll x, y, k;
    cin >> x >> y >> k;

    ll g = gcd(x, y);
    x /= g, y /= g;

    if (!check_div(x, k) || !check_div(y, k)) {
        cout << -1 << '\n';
        return;
    }

    ll ans = calc_step(x, k) + calc_step(y, k);
    if (ans < LLONG_MAX / 2) {
        cout << ans << '\n';
    } else {
        cout << -1 << '\n';
    }
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // init();

    ll t;
    cin >> t;
    while (t--)
        solve2();

    return 0;
};