#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using iPair = pair<int,int>;
using lPair = pair<ll, ll>;
using ivector = vector<int>;
using lvector = vector<ll>;
using istack = stack<int>;
using iqueue = queue<int>;
using ivv = vector<vector<int>>;
using lvv = vector<vector<ll>>;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
vector<iPair> dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};
#define dump(x) cout << #x << " = " << (x) << endl
#define ALL(x) begin(x),end(x)
#define rep(i,s,e) for(ll i=(s), i_stop=(e); i<i_stop; ++i)
#define repRev(i,s,e) for(ll i=(e)-1, i_stop=(s); i>=i_stop; --i)
#define range(i,s,n) for(ll i=(s), i_stop=(s)+(n); i<i_stop; ++i)
#define rangeRev(i,s,n) for(ll i=(s), i_stop=(s)-(n); i>i_stop; --i)
#define foreach(x,container) for(auto &&x:container)
template<typename T> bool chmax(T& a, const T b) {if(a<b) {a=b;return true;} return false;}
template<typename T> bool chmin(T& a, const T b) {if(a>b) {a=b;return true;} return false;}
template<typename T> void printArr(vector<T> &arr){
    for(auto &x:arr) {cout << x << " ";} cout << endl;
}

// ===================================================================

/*

*/

lvector prime;
lvector cnt;
map<ll,ll> fac;

ll get_cnt(ll x) {
    ll ans = 0;
    for(auto it = fac.rbegin(); it != fac.rend(); ++it) {
        ll base = it->first; ll expo = it->second;
        if(x % base == 0) {
            x /= base; ans += expo;
        }
    }
    return ans + (x!=1);
}

ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

bool check(ll a, ll b, ll k) {
    ll ax = get_cnt(a);
    ll bx = get_cnt(b);
    if(k > ax+bx) return false;

    ll g = gcd(a,b);
    if(a == b) {return k!=1;}
    if(a == g || b == g) {return k >= 1;}
    return k >= 2;
}

void solve() {
    ll maxn = 1000000000LL;
    vector<bool> flag(35000, true);
    cnt = lvector(35000, 0);

    for(ll i = 2; i*i <= maxn; ++i) if(flag[i]) {
        prime.push_back(i);
        // 更新所有 kn 的 flag
        for(ll j = i*i; j*j <= maxn; j += i) if(flag[j]) flag[j] = false;
        // 更新所有 i^k 的 cnt
        for(ll j = i; j*j <= maxn; j *= i) {
            cnt[j] += 1 + cnt[j/i];
            fac[j] = cnt[j];
        }
    }


    int t; cin>>t;
    while(t--) {
        ll a,b,k; cin>>a>>b>>k;
        cout << (check(a,b,k)?"Yes":"No") << endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

You are given two integers a and b. In one turn, you can do one of the following operations: 

  * Take an integer c (c > 1 and a should be divisible by c) and replace a with a/c; 
  * Take an integer c (c > 1 and b should be divisible by c) and replace b with b/c. 



Your goal is to make a equal to b using exactly k turns.

For example, the numbers a=36 and b=48 can be made equal in 4 moves: 

  * c=6, divide b by c ⇒ a=36, b=8; 
  * c=2, divide a by c ⇒ a=18, b=8; 
  * c=9, divide a by c ⇒ a=2, b=8; 
  * c=4, divide b by c ⇒ a=2, b=2. 



For the given numbers a and b, determine whether it is possible to make them equal using exactly k turns.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

Each test case is contains three integers a, b and k (1 ≤ a, b, k ≤ 10^9).

Output

For each test case output: 

  * "Yes", if it is possible to make the numbers a and b equal in exactly k turns; 
  * "No" otherwise. 



The strings "Yes" and "No" can be output in any case.

Example

Input


8
36 48 2
36 48 3
36 48 4
2 8 1
2 8 2
1000000000 1000000000 1000000000
1 2 1
2 2 1


Output


YES
YES
YES
YES
YES
NO
YES
NO

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using iPair = pair<int,int>;
using lPair = pair<ll, ll>;
using ivector = vector<int>;
using lvector = vector<ll>;
using istack = stack<int>;
using iqueue = queue<int>;
using ivv = vector<vector<int>>;
using lvv = vector<vector<ll>>;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
vector<iPair> dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};
#define dump(x) cout << #x << " = " << (x) << endl
#define ALL(x) begin(x),end(x)
#define rep(i,s,e) for(ll i=(s), i_stop=(e); i<i_stop; ++i)
#define repRev(i,s,e) for(ll i=(e)-1, i_stop=(s); i>=i_stop; --i)
#define range(i,s,n) for(ll i=(s), i_stop=(s)+(n); i<i_stop; ++i)
#define rangeRev(i,s,n) for(ll i=(s), i_stop=(s)-(n); i>i_stop; --i)
#define foreach(x,container) for(auto &&x:container)
template<typename T> bool chmax(T& a, const T b) {if(a<b) {a=b;return true;} return false;}
template<typename T> bool chmin(T& a, const T b) {if(a>b) {a=b;return true;} return false;}
template<typename T> void printArr(vector<T> &arr){
    for(auto &x:arr) {cout << x << " ";} cout << endl;
}

// ===================================================================

/*

*/

lvector prime;
lvector cnt;
map<ll,ll> fac;

ll get_cnt(ll x) {
    ll ans = 0;
    for(auto it = fac.rbegin(); it != fac.rend(); ++it) {
        ll base = it->first; ll expo = it->second;
        if(x % base == 0) {
            x /= base; ans += expo;
        }
    }
    return ans + (x!=1);
}

ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

bool check(ll a, ll b, ll k) {
    ll ax = get_cnt(a);
    ll bx = get_cnt(b);
    if(k > ax+bx) return false;

    ll g = gcd(a,b);
    if(a == b) {return k!=1;}
    if(a == g || b == g) {return k >= 1;}
    return k >= 2;
}

void solve() {
    ll maxn = 1000000000LL;
    vector<bool> flag(35000, true);
    cnt = lvector(35000, 0);

    for(ll i = 2; i*i <= maxn; ++i) if(flag[i]) {
        prime.push_back(i);
        // 更新所有 kn 的 flag
        for(ll j = i*i; j*j <= maxn; j += i) if(flag[j]) flag[j] = false;
        // 更新所有 i^k 的 cnt
        for(ll j = i; j*j <= maxn; j *= i) {
            cnt[j] += 1 + cnt[j/i];
            fac[j] = cnt[j];
        }
    }


    int t; cin>>t;
    while(t--) {
        ll a,b,k; cin>>a>>b>>k;
        cout << (check(a,b,k)?"Yes":"No") << endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}
```