#include<bits/stdc++.h>
using namespace std;

#define fast_io ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define pb push_back
#define ff first
#define ss second
const long long mod = 1e9+7;
const long long INF = LLONG_MAX;
const long long NINF = LLONG_MIN;

const int N = 100000;
int lp[N+1];
vector<int> pr;

void compute() {
    for (int i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }
        for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
        }
}

int fac(long long n) {
    int factor = 0;
    for (long long d : pr) {
        if (d * d > n)
            break;
        while (n % d == 0) {
            factor++;
            n /= d;
        }
    }
    if (n > 1)
        factor++;
    return factor;
}



signed main()
{                    
    fast_io;
    compute();

    int t;
    cin >> t;
    while(t--) {
        int a, b, k;
        cin >> a >> b >> k;

        int l = 2;
        int r = fac(a) + fac(b);

        if(a == b and k == 1) {
            cout << "NO\n";
            continue;
        }

        if(max(a,b) % min(a,b) == 0) {
            l = 1;
        }

        if(k >= l and k <= r) cout << "YES\n";
        else cout << "NO\n";    

    }
}
### Prompt

Please formulate a CPP solution to the following problem:

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;

#define fast_io ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define pb push_back
#define ff first
#define ss second
const long long mod = 1e9+7;
const long long INF = LLONG_MAX;
const long long NINF = LLONG_MIN;

const int N = 100000;
int lp[N+1];
vector<int> pr;

void compute() {
    for (int i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }
        for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
        }
}

int fac(long long n) {
    int factor = 0;
    for (long long d : pr) {
        if (d * d > n)
            break;
        while (n % d == 0) {
            factor++;
            n /= d;
        }
    }
    if (n > 1)
        factor++;
    return factor;
}



signed main()
{                    
    fast_io;
    compute();

    int t;
    cin >> t;
    while(t--) {
        int a, b, k;
        cin >> a >> b >> k;

        int l = 2;
        int r = fac(a) + fac(b);

        if(a == b and k == 1) {
            cout << "NO\n";
            continue;
        }

        if(max(a,b) % min(a,b) == 0) {
            l = 1;
        }

        if(k >= l and k <= r) cout << "YES\n";
        else cout << "NO\n";    

    }
}
```