Another problem about dividing numbers (Cf)

//https://codeforces.com/contest/1538/problem/D


#include<bits/stdc++.h>
using namespace std;
#define forx(x1,y1) for( unsigned long long x1=0;x1<y1;++x1)
#define INF 1e9
#define all(x2) begin(x2),end(x2)
using ll= double;
using ull=unsigned long long;
vector<ull>v;
map<ull,ull>m;
ull gcd (ull a, ull b) {
    return b ? gcd (b, a % b) : a;
}
void f(){
    v.push_back(2);
    v.push_back(3);
    for(ull i=5;i*i<=ull(1e9);++i){
        bool b =true;
        for(ull j=2;j*j<=i;++j)
            if(i%j==0){
                b=false;
                break;
            }
        if(b)
            v.push_back(i);
    }
}
ull g(ull x){
    ull kmax=0;
    for(ull& i:v){
        while(x%i==0){
            ++m[i];
            x/=i;
        }
        if(x==1)
            break;
    }
    for(auto&[_,p]:m){
        kmax+=p;
    }
    m.clear();
    if (x!=1)
        ++kmax;
    return kmax;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie();
    ull t;
    f();
    cin>>t;
    vector<string>ot;
    while(t-->0){
        ull a,b;
        cin>>a>>b;
        ull kmin,kmax;
        ull de=gcd(a,b);
        if(a==b)
            kmin=0;
        else {
            if (de == a || de == b)
                kmin = 1;
            else
                kmin = 2;
        }
        kmax=g(a);
        kmax+=g(b);
        ull k;
        cin>>k;
        if(a==b && k==1){
            ot.emplace_back("NO");
            continue;
        }
        if (k >= kmin && k <= kmax)
            ot.emplace_back("YES");
        else
            ot.emplace_back("NO");
    }
    for(auto& i:ot)
        cout<<i<<'\n';
}