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

#define int long long int
#define P pair<int,int>
#define pb push_back
#define F first
#define S second
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void online_judge()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

const int N = 32005;

int pr[N];
vector<int> primes;
 
void sieve() {
    int i, j;
    primes.pb(2ll);
    for (i = 3; i < N; i+=2) {
        if (!pr[i]) {
            primes.pb(i);
            for (j = i*i; j < N; j += i) {
                pr[j]++;
            }
        }
    }
}

int factorisation(int n){
    int cnt=0;
    for(auto x: primes){
        if(n==1){
            break;
        }
        while(n%x==0){
            n/=x;
            cnt++;
        }
    }
    if(n!=1){
        cnt++;
    }
    return cnt;
}

int32_t main(){

    FIO;
    online_judge();
	
	sieve();
    int t; cin>>t; while(t--)
    {
            int a,b,c;

            cin>>a>>b>>c;
            
            int sum=factorisation(a);
            sum+=factorisation(b);

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

            int lowest=0;

            if(a!=b)
            {
                lowest++;
                if((a%b)&&(b%a))
                    lowest++;
            }


           


            if(c>=lowest&&c<=sum)
            {
                cout<<"YES\n";
            }
            else cout<<"NO\n";

    }
    return 0;
}

### 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 int long long int
#define P pair<int,int>
#define pb push_back
#define F first
#define S second
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void online_judge()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

const int N = 32005;

int pr[N];
vector<int> primes;
 
void sieve() {
    int i, j;
    primes.pb(2ll);
    for (i = 3; i < N; i+=2) {
        if (!pr[i]) {
            primes.pb(i);
            for (j = i*i; j < N; j += i) {
                pr[j]++;
            }
        }
    }
}

int factorisation(int n){
    int cnt=0;
    for(auto x: primes){
        if(n==1){
            break;
        }
        while(n%x==0){
            n/=x;
            cnt++;
        }
    }
    if(n!=1){
        cnt++;
    }
    return cnt;
}

int32_t main(){

    FIO;
    online_judge();
	
	sieve();
    int t; cin>>t; while(t--)
    {
            int a,b,c;

            cin>>a>>b>>c;
            
            int sum=factorisation(a);
            sum+=factorisation(b);

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

            int lowest=0;

            if(a!=b)
            {
                lowest++;
                if((a%b)&&(b%a))
                    lowest++;
            }


           


            if(c>=lowest&&c<=sum)
            {
                cout<<"YES\n";
            }
            else cout<<"NO\n";

    }
    return 0;
}

```