#include <bits/stdc++.h>
#define M 1000000007
#define fio                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define d(x) cout << #x << " " << x << "\n";
#define min(x1, x2) (x1 > x2 ? x2 : x1)
#define max(x1, x2) (x1 < x2 ? x2 : x1)
#define min3(x1, x2, x3) (x3 > min(x1, x2) ? min(x2, x1) : x3)
#define max3(x1, x2, x3) (x3 < max(x1, x2) ? max(x1, x2) : x3)
#define ll long long int
#define ul unsigned long long int
#define p pair<ll, ll>
#define ld long double
#define dv(v)                            \
    cerr << #v << "  ";                  \
    for (int i = 0; i < (v).size(); i++) \
        cerr << v[i] << " ";             \
    cerr << "\n";
#define inf INT_MAX
#define mp(x, y) make_pair(x, y)
using namespace std;

vector<bool> prime;
vector<int> spf;
vector<int> pr;
void sieve(int n) // o(nlnln(sqrt(n)))
{
    prime.assign(n + 1, true);
    prime[0] = prime[1] = false;
    spf.resize(n + 1, 0);
    for (ll i = 2; i <= n; i++)
    {
        if (prime[i])
        {
            spf[i] = i;
            for (ll j = i * i; j <= n; j += i)
            {
                prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        if (prime[i])
        {
            pr.push_back(i);
        }
    }
}
ll fac(ll y)
{
    ll j = y;
    ll tm = 0;
    ll x;
    for (int i = 0; i < pr.size(); ++i)
    {
        while (j % pr[i] == 0)
        {
            j /= pr[i];
            ++tm;
        }
    }
    if (j!=1)
    {
        ++tm;
    }
    return tm;
}

int main()
{
    fio;
    sieve(1e5);
    ll t, n, x, y, z, k, z2;
    cin >> t;
    while (t--)
    {
        cin >> x >> y >> k;
        if (k == 1 && x == y)
        {
            cout << "NO\n";
            continue;
        }
        else if (k == 1 && (x % y == 0 || y % x == 0) && x != y)
        {
            cout << "YES\n";
            continue;
        }
        else if (k == 1)
        {
            cout << "NO\n";
            continue;
        }
        int k0 = fac(x) + fac(y);
        if (k <= k0 && k >= 2)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
    return 0;
}
### Prompt

Your challenge is to write 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>
#define M 1000000007
#define fio                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define d(x) cout << #x << " " << x << "\n";
#define min(x1, x2) (x1 > x2 ? x2 : x1)
#define max(x1, x2) (x1 < x2 ? x2 : x1)
#define min3(x1, x2, x3) (x3 > min(x1, x2) ? min(x2, x1) : x3)
#define max3(x1, x2, x3) (x3 < max(x1, x2) ? max(x1, x2) : x3)
#define ll long long int
#define ul unsigned long long int
#define p pair<ll, ll>
#define ld long double
#define dv(v)                            \
    cerr << #v << "  ";                  \
    for (int i = 0; i < (v).size(); i++) \
        cerr << v[i] << " ";             \
    cerr << "\n";
#define inf INT_MAX
#define mp(x, y) make_pair(x, y)
using namespace std;

vector<bool> prime;
vector<int> spf;
vector<int> pr;
void sieve(int n) // o(nlnln(sqrt(n)))
{
    prime.assign(n + 1, true);
    prime[0] = prime[1] = false;
    spf.resize(n + 1, 0);
    for (ll i = 2; i <= n; i++)
    {
        if (prime[i])
        {
            spf[i] = i;
            for (ll j = i * i; j <= n; j += i)
            {
                prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        if (prime[i])
        {
            pr.push_back(i);
        }
    }
}
ll fac(ll y)
{
    ll j = y;
    ll tm = 0;
    ll x;
    for (int i = 0; i < pr.size(); ++i)
    {
        while (j % pr[i] == 0)
        {
            j /= pr[i];
            ++tm;
        }
    }
    if (j!=1)
    {
        ++tm;
    }
    return tm;
}

int main()
{
    fio;
    sieve(1e5);
    ll t, n, x, y, z, k, z2;
    cin >> t;
    while (t--)
    {
        cin >> x >> y >> k;
        if (k == 1 && x == y)
        {
            cout << "NO\n";
            continue;
        }
        else if (k == 1 && (x % y == 0 || y % x == 0) && x != y)
        {
            cout << "YES\n";
            continue;
        }
        else if (k == 1)
        {
            cout << "NO\n";
            continue;
        }
        int k0 = fac(x) + fac(y);
        if (k <= k0 && k >= 2)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
    return 0;
}
```