/*
 *
 * FILE: C.cpp
 *
 * Institution : Hajee Mohammad Danesh Science and Technology University,Dinajpur,Bangladesh (H S T U).
 *
 * Name        : Sourav Roy (Shuvo)
 *
 * Department  : Computer Science and Engineering (Batch - CSE'19)
 *
 * Email       : souravkumarroy813965@gmail.com
 *
 */

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define all(a) a.begin(),a.end()
#define pb push_back
#define mod 1000000007
#define mx  5000008
bool marked[mx];
vector <int> primes;

void sieve()
{
    int i,j;
    primes.pb(2);

    for(i=3; i*i<=mx; i+=2)
    {
        if(marked[i]==false)
        {
            for(j=i*i; j<=mx; j+=(i+i))
            {
                marked[j] = true;
            }
        }
    }

    for(i=3; i<=mx; i+=2)
    {
        if(marked[i]==false)
        {
            primes.pb(i);
        }
    }

}

int PrimeFactorization(int x)
{
    int i,j,cn=0;

    for(i=0; primes[i]*primes[i]<=x; i++)
    {
        while(x%primes[i]==0)
        {
            cn++;
            x/=primes[i];
        }
    }
    if(x>1)
    {
        cn++;
    }
    return cn;
}


void solve()
{
    int a,b,k,i,x,ans=-1,y,l,r;
    cin >> a >> b >> k;
    if(k==1)
    {
        if(a==b)
        {
            cout << "NO" << endl;
        }
        else if(a==1 || b==1)
        {
            cout << "YES" << endl;
        }
        else if(a%b==0 || b%a==0)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    else if(a==b)
    {
        x = PrimeFactorization(a);
        if(k>=2 && k<=2*x)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    else
    {
        l = PrimeFactorization(a);
        r = PrimeFactorization(b);
        if(l+r>=k)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    sieve();
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
}
/**
Test Case :

**/

### Prompt

Develop a solution in cpp to the problem described below:

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
/*
 *
 * FILE: C.cpp
 *
 * Institution : Hajee Mohammad Danesh Science and Technology University,Dinajpur,Bangladesh (H S T U).
 *
 * Name        : Sourav Roy (Shuvo)
 *
 * Department  : Computer Science and Engineering (Batch - CSE'19)
 *
 * Email       : souravkumarroy813965@gmail.com
 *
 */

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define all(a) a.begin(),a.end()
#define pb push_back
#define mod 1000000007
#define mx  5000008
bool marked[mx];
vector <int> primes;

void sieve()
{
    int i,j;
    primes.pb(2);

    for(i=3; i*i<=mx; i+=2)
    {
        if(marked[i]==false)
        {
            for(j=i*i; j<=mx; j+=(i+i))
            {
                marked[j] = true;
            }
        }
    }

    for(i=3; i<=mx; i+=2)
    {
        if(marked[i]==false)
        {
            primes.pb(i);
        }
    }

}

int PrimeFactorization(int x)
{
    int i,j,cn=0;

    for(i=0; primes[i]*primes[i]<=x; i++)
    {
        while(x%primes[i]==0)
        {
            cn++;
            x/=primes[i];
        }
    }
    if(x>1)
    {
        cn++;
    }
    return cn;
}


void solve()
{
    int a,b,k,i,x,ans=-1,y,l,r;
    cin >> a >> b >> k;
    if(k==1)
    {
        if(a==b)
        {
            cout << "NO" << endl;
        }
        else if(a==1 || b==1)
        {
            cout << "YES" << endl;
        }
        else if(a%b==0 || b%a==0)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    else if(a==b)
    {
        x = PrimeFactorization(a);
        if(k>=2 && k<=2*x)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    else
    {
        l = PrimeFactorization(a);
        r = PrimeFactorization(b);
        if(l+r>=k)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    sieve();
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
}
/**
Test Case :

**/

```