#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int c = 0;
vector<int> primes;
void factors(int n)
{
    for (int i = 0; i < (int)primes.size(); ++i) {
        while (n % primes[i] == 0) {
            n /= primes[i];
            c++;
        }
    }
    if (n > 1)c++;
}
void solve() {
    int a, b, k; cin >> a >> b >> k;
    c = 0;
    if (k == 1) {
        if (a == b) {
            cout << "NO" << endl;
            return;
        }
        else {
            if (a > b) swap(a, b);
            if (b % a == 0) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
                return;
            }
        }
    }
    else {
        factors(a);
        factors(b);
        if (k <= c) {
            cout << "YES" << endl;
            return;
        }
        else {
            cout << "NO" << endl;
        }
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

#ifndef ONLINE_JUDGE
    freopen("input1.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
#endif
    int n = 32000;
    vector<bool> p(n + 1, true);
    for (int i = 2; i <= n; ++i) {
        if (!p[i]) continue;
        primes.push_back(i);
        for (int j = 2 * i; j <= n; j += i) {
            p[j] = 0;
        }
    }
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        solve();
    }
}

### Prompt

In CPP, your task is to solve 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
#define endl '\n'
int c = 0;
vector<int> primes;
void factors(int n)
{
    for (int i = 0; i < (int)primes.size(); ++i) {
        while (n % primes[i] == 0) {
            n /= primes[i];
            c++;
        }
    }
    if (n > 1)c++;
}
void solve() {
    int a, b, k; cin >> a >> b >> k;
    c = 0;
    if (k == 1) {
        if (a == b) {
            cout << "NO" << endl;
            return;
        }
        else {
            if (a > b) swap(a, b);
            if (b % a == 0) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
                return;
            }
        }
    }
    else {
        factors(a);
        factors(b);
        if (k <= c) {
            cout << "YES" << endl;
            return;
        }
        else {
            cout << "NO" << endl;
        }
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

#ifndef ONLINE_JUDGE
    freopen("input1.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
#endif
    int n = 32000;
    vector<bool> p(n + 1, true);
    for (int i = 2; i <= n; ++i) {
        if (!p[i]) continue;
        primes.push_back(i);
        for (int j = 2 * i; j <= n; j += i) {
            p[j] = 0;
        }
    }
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        solve();
    }
}

```