CF ROUND 1027 F

// Problem: F. Small Operations
// Contest: Codeforces - Codeforces Round  1027 (Div. 3)
// URL: https://codeforces.com/contest/2114/problem/F
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

namespace rngs = std::ranges;
using ll = long long;
using a2l = array<ll, 2>;
using pll = pair<ll, ll>;
using vl = vector<ll>;

constexpr ll ub = 1e6 + 3;
vector<vl> divs(ub);
void init()
{
    for (ll i = 1; i < ub; ++i)
        for (ll j = i; j < ub; j += i)
            divs[j].push_back(i);
}

void solve(ll t)
{
    ll x, y, k, ans = 0;
    cin >> x >> y >> k;

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

    auto remove_req = [&ans, k](ll val) -> ll {
        dbg(val);
        assert(val < ub);
        const auto &ds = divs[val];
        ll len = divs[val].size();
        vl cost(len, LLONG_MAX / 2);
        cost[0] = 0;

        for (ll i = 1; i < len; ++i)
            for (ll j = 0; j < i; ++j)
                if (ds[i] % ds[j] == 0 && ds[i] <= ds[j] * k)
                    cost[i] = min(cost[i], cost[j] + 1);
        return cost.back();
    };
    ans = remove_req(x) + remove_req(y);
    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;
    ll ot = t;
    while (t--)
        solve(ot - t);

    return 0;
};