#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mxN 100001
vector<int> prime(mxN, 1);
bool findPrime(int n)
{
    if(n==1)
        return 0;
	if(n==2 || n==3)
        return 1;
    if(n%2==0 || n%3==0)
        return 0;
    int i=5,k=2;
    while(i*i<=n)
    {
        if(n%i==0)
          return 0;
        i=i+k;
        k=6-k;
    }
    return 1;
}
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
     
}
 
void sieve()   
{   
    for (int p = 2; p * p < mxN; p++)
    {
        if(prime[p] == 1)
        {
            for (int i = p * p; i < mxN; i += p)
                prime[i] = 0;
        }
    }  
}
signed main()
{
    int t;
    cin>>t;
    sieve();
    vector<int> A;
    for(int i=2; i<mxN; i++)
    {
        if(prime[i])
        {
            A.push_back(i);
        }
    }
    while(t--)
    {
        int a,b,k;
        cin>>a>>b>>k;
        
        if(a>b)
        {
            swap(a,b);
        }
        if(k==1)
        {
            if(a==b)
            {
                cout<<"NO"<<endl;
            }
            else if(gcd(a,b)==a)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else 
        {
            int count = 0;
            for(int i=0; i<A.size(); i++)
            {
                while(a>1 && a%A[i]==0)
                {
                    a=a/A[i];
                    count++;
                }
                while(b>1 && b%A[i]==0)
                {
                    b=b/A[i];
                    count++;
                }
            }
            if(a>1)
            {
                count++;
            }
            if(b>1)
            {
                count++;
            }
            if(count>=k)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        
    }

}
### 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;
#define int long long
#define mxN 100001
vector<int> prime(mxN, 1);
bool findPrime(int n)
{
    if(n==1)
        return 0;
	if(n==2 || n==3)
        return 1;
    if(n%2==0 || n%3==0)
        return 0;
    int i=5,k=2;
    while(i*i<=n)
    {
        if(n%i==0)
          return 0;
        i=i+k;
        k=6-k;
    }
    return 1;
}
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
     
}
 
void sieve()   
{   
    for (int p = 2; p * p < mxN; p++)
    {
        if(prime[p] == 1)
        {
            for (int i = p * p; i < mxN; i += p)
                prime[i] = 0;
        }
    }  
}
signed main()
{
    int t;
    cin>>t;
    sieve();
    vector<int> A;
    for(int i=2; i<mxN; i++)
    {
        if(prime[i])
        {
            A.push_back(i);
        }
    }
    while(t--)
    {
        int a,b,k;
        cin>>a>>b>>k;
        
        if(a>b)
        {
            swap(a,b);
        }
        if(k==1)
        {
            if(a==b)
            {
                cout<<"NO"<<endl;
            }
            else if(gcd(a,b)==a)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        else 
        {
            int count = 0;
            for(int i=0; i<A.size(); i++)
            {
                while(a>1 && a%A[i]==0)
                {
                    a=a/A[i];
                    count++;
                }
                while(b>1 && b%A[i]==0)
                {
                    b=b/A[i];
                    count++;
                }
            }
            if(a>1)
            {
                count++;
            }
            if(b>1)
            {
                count++;
            }
            if(count>=k)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
        
    }

}
```