CF ROUND 1027 F AC

// 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>;

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];
}

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

vl get_factor(ll x, ll k)
{
    vl ret{1, x};
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            ret.push_back(i);
            if (i != x / i)
                ret.push_back(x / i);
        }
    }
    rngs::sort(ret);
    return ret;
}

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

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);
    ll ans = calc_step2(x, k) + calc_step2(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);

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

    return 0;
};