//~ author      : Sumit Prajapati
#include <bits/stdc++.h>
using namespace std;


// #define int                 long long           
#define curtime             chrono::high_resolution_clock::now()
#define timedif(start,end)  chrono::duration_cast<chrono::nanoseconds>(end - start).count()
auto time0=curtime;


int bin_power(int a,int b,int md){
    int res=1;
    while (b){
        if (b&1)
            res=(1LL*res*a)%md;
        a=(1LL*a*a)%md;
        b>>=1;
    }
    return res;
}
bool probablyPrimeFermat(int n, int iter=8) {
    if (n < 4)
        return n == 2 || n == 3;

    for (int i = 0; i < iter; i++) {
        int a = 2 + rand() % (n - 3);
        if (bin_power(a, n - 1, n) != 1)
            return false;
    }
    return true;
} 
 
 
void solve(){
  
    int a,b,k;
    cin>>a>>b>>k;
    if(k==1){
        if(a==b)
            cout<<"NO\n";
        else if(a%b==0 || b%a==0)
            cout<<"YES\n";
        else
            cout<<"NO\n";
        return;
    }
    int a_sum=0,b_sum=0;
    if(probablyPrimeFermat(a))
        a_sum+=1,a=1;
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            int cnt=0;
            while(a%i==0)
                a/=i,cnt++;
            a_sum+=cnt;
        }
    }  
    if(a>1)
        a_sum+=1;
    if(probablyPrimeFermat(b))
        b_sum+=1,b=1;
    for(int i=2;i*i<=b;i++){
        if(b%i==0){
            int cnt=0;
            while(b%i==0)
                b/=i,cnt++;
            b_sum+=cnt;
        }
    }  
    if(b>1)
        b_sum+=1;
    cout<<((a_sum+b_sum)>=k?"YES\n":"NO\n");
 
} 
 
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    time0 = curtime;
    srand(time(NULL));
    int t=1;
    cin>>t;
    while(t--){
        // cout<<"Case #"<<tt<<": ";
        solve();
    }
    
    cerr<<"Execution Time: "<<timedif(time0,curtime)*1e-9<<" sec\n";
    return 0;
 
}
### Prompt

Generate 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
//~ author      : Sumit Prajapati
#include <bits/stdc++.h>
using namespace std;


// #define int                 long long           
#define curtime             chrono::high_resolution_clock::now()
#define timedif(start,end)  chrono::duration_cast<chrono::nanoseconds>(end - start).count()
auto time0=curtime;


int bin_power(int a,int b,int md){
    int res=1;
    while (b){
        if (b&1)
            res=(1LL*res*a)%md;
        a=(1LL*a*a)%md;
        b>>=1;
    }
    return res;
}
bool probablyPrimeFermat(int n, int iter=8) {
    if (n < 4)
        return n == 2 || n == 3;

    for (int i = 0; i < iter; i++) {
        int a = 2 + rand() % (n - 3);
        if (bin_power(a, n - 1, n) != 1)
            return false;
    }
    return true;
} 
 
 
void solve(){
  
    int a,b,k;
    cin>>a>>b>>k;
    if(k==1){
        if(a==b)
            cout<<"NO\n";
        else if(a%b==0 || b%a==0)
            cout<<"YES\n";
        else
            cout<<"NO\n";
        return;
    }
    int a_sum=0,b_sum=0;
    if(probablyPrimeFermat(a))
        a_sum+=1,a=1;
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            int cnt=0;
            while(a%i==0)
                a/=i,cnt++;
            a_sum+=cnt;
        }
    }  
    if(a>1)
        a_sum+=1;
    if(probablyPrimeFermat(b))
        b_sum+=1,b=1;
    for(int i=2;i*i<=b;i++){
        if(b%i==0){
            int cnt=0;
            while(b%i==0)
                b/=i,cnt++;
            b_sum+=cnt;
        }
    }  
    if(b>1)
        b_sum+=1;
    cout<<((a_sum+b_sum)>=k?"YES\n":"NO\n");
 
} 
 
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    time0 = curtime;
    srand(time(NULL));
    int t=1;
    cin>>t;
    while(t--){
        // cout<<"Case #"<<tt<<": ";
        solve();
    }
    
    cerr<<"Execution Time: "<<timedif(time0,curtime)*1e-9<<" sec\n";
    return 0;
 
}
```