CF1538D

// Problem: D. Another Problem About Dividing Numbers
// Contest: Codeforces - Codeforces Round 725 (Div. 3)
// URL: https://codeforces.com/problemset/problem/1538/D
// Memory Limit: 256 MB
// Time Limit: 2000 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>>;

using ll = long long;
using a2l = array<ll, 2>;
using pll = pair<ll, ll>;
using vl = vector<ll>;

constexpr ll ub = 1e5 + 3;
vl ps, np(ub), pf(ub);

void init()
{
    for (ll i = 2; i < ub; ++i) {
        if (np[i] == 0) {
            ps.push_back(i);
            pf[i] = i;
        }
        for (auto x : ps) {
            if (i * x >= ub)
                break;
            np[i * x] = 1;
            pf[i * x] = x;
            if (i % x == 0)
                break;
        }
    }
}

ll get_fcnt(ll v)
{
    ll ret = 0;
    if (v > ub) {
        for (auto x : ps) {
            while (v % x == 0) {
                v /= x;
                ret += 1;
            }
        }
        if (v > ub)
            return ret + 1;
    }
    while (v != 1) {
        v /= pf[v];
        ret += 1;
    }
    return ret;
};

void solve()
{
    ll a, b, k;
    cin >> a >> b >> k;
    ll g = gcd(a, b), l = lcm(a, b);
    // ll min_op = a != b ? (a / g != 1) + (b / g != 1) : 0;
    ll min_op = a == b ? 0 : (g == a || g == b ? 1 : 2);
    ll max_op = get_fcnt(a) + get_fcnt(b);
    // cout << (min_op <= k && k <= max_op ? "YES" : "NO") << '\n';
    /*
    if (min_op <= k && k <= max_op) {
        if (k == 1 && min_op == 1) {
            cout << "YES" << '\n';
        } else if (k != 1) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }
    } else {
        cout << "NO" << '\n';
    }
    */
    dbg(min_op, k, max_op);
    if (min_op <= k && k <= max_op) {
        if (k != 1 || min_op == 1) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }
    } else {
        cout << "NO" << '\n';
    }
}

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

    ll t;
    cin >> t;
    init();
    while (t--)
        solve();
    return 0;
};