// ?-------------------------------------------------------------------------------------------------
// !                                         Shubham Lohan
// ?-------------------------------------------------------------------------------------------------

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

//! ------------------------------------------- Macros ----------------------------------------------

typedef long long ll;
typedef long double lld;

#define setbits(x) __builtin_popcountll(x)  // to count no of 1's
#define sp(x, y) fixed << setprecision(y) << x
#define flush fflush(stdout)
#define all(x) x.begin(), x.end()
#define nline "\n"
#define yes cout << "YES" << nline
#define no cout << "NO" << nline
#define vi vector<int>
#define mii map<int, int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define For(n) for (int i = 0; i < n; i++)
#define inf 1e9
const int MOD = 1e9 + 7;
//! ------------------------------------------ Debugger ---------------------------------------------

template <typename T>
void __print(const T &x);
void __print(const int &x) { cerr << x; }
void __print(const ll &x) { cerr << x; }
void __print(const lld &x) { cerr << x; }
void __print(const float &x) { cerr << x; }
void __print(const double &x) { cerr << x; }
void __print(const char &x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(const bool &x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) { cerr << '(', __print(x.first), cerr << ',', __print(x.second), cerr << ')'; }
template <typename T>
void __print(const T &x) {
    int c = 0;
    cerr << "{";
    for (auto i : x) cerr << (c++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define deb(x...)               \
    cerr << "[" << #x << ":  "; \
    _print(x)
#else
#define deb(x...)
#endif

//! ----------------------------------------- Algorithms --------------------------------------------

template <typename T, typename V>
float divide(T a, V b) { return (float)a / (float)b; }
bool isPrime(int n) {  //! time complexity O(sqrt(N))
    if (n <= 1)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}
vector<bool> sieve(int n) {
    vector<bool> prime(n + 1, true);
    prime[0] = false, prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= n; j += i)
                prime[j] = false;
        }
    }
    return prime;
}
vector<int> sieve_primeFactor(int n) {
    //! prime factorization using sieve
    vector<int> prime(n + 1);
    prime[1] = 1;
    for (int i = 2; i <= n; i++)
        prime[i] = i;
    for (int i = 4; i <= n; i += 2)
        prime[i] = 2;

    for (int i = 3; i * i <= n; i += 2) {
        if (prime[i] == i) {
            for (int j = i * i; j <= n; j += i) {
                if (prime[j] == j)
                    prime[j] = i;
            }
        }
    }
    return prime;
}
vector<int> prime_factor(int n, vector<int> &prime) {
    vector<int> factors;
    while (prime[n] != 1)
        factors.push_back(prime[n]), n = n / prime[n];
    if (n > 1) factors.push_back(n);
    return factors;
}
int phi(int n) {
    // ? finding Euler's totient function Φ(N) in O(sqrt(N)) time
    int result = n;
    if (n % 2 == 0) {
        result /= 2;
        while (n % 2 == 0)
            n /= 2;
    }
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result /= i, result *= (i - 1);
        }
    }
    if (n > 1)
        result /= n, result *= (n - 1);
    return result;
}
int power(int x, int n, int mod = MOD) {
    // ! used to calculate x^n in O(logn)
    int result = 1;
    while (n) {
        if (n & 1)  // odd
            result = (result * x) % mod, n--;
        x = (x * x) % mod, n = n >> 1;  // floor(n/2)
    }
    return result;
}
int modular_inverse(int x, int n) { return power(x, n - 2, n); }
vector<int> fact_mod(int n, int mod) {
    //? finding n! % mod
    vector<int> fact(n + 1);
    fact[0] = fact[1] = 1;
    for (int i = 2; i < fact.size(); i++)
        fact[i] = (fact[i - 1] * i) % mod;
    return fact;
}
int combination(int n, int k, const vector<int> &fact, int mod) {
    //! finding nCr % mod
    if (k > n)
        return 0;
    int result = fact[n];
    result = (result * modular_inverse(fact[k], mod)) % mod;
    result = (result * modular_inverse(fact[n - k], mod)) % mod;
    return result;
}
int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x1, y1;
    int d = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
int wheel(int n) {
    vector<int> factorization;
    int count = 0;
    for (int d : {2, 3, 5}) {
        while (n % d == 0) {
            // factorization.push_back(d);
            count++;
            n /= d;
        }
    }
    static array<int, 8> increments = {4, 2, 4, 2, 4, 6, 2, 6};
    int i = 0;
    for (int d = 7; d * d <= n; d += increments[i++]) {
        while (n % d == 0) {
            // factorization.push_back(d);
            count++;
            n /= d;
        }
        if (i == 8)
            i = 0;
    }
    if (n > 1) {
        // factorization.push_back(n);
        count++;
    }
    return count;
    // return factorization;
}
auto Compare = [](const int &a, const int &b) { return a > b; };

// !-------------------------------------------------------------------------------------------------
// ?                                           Solution
// !-------------------------------------------------------------------------------------------------

void solve() {
    int a, b, k;
    cin >> a >> b >> k;
    int ans = wheel(a);
    ans += wheel(b);

    if (k == 1) {
        if (a == b) {
            no;
            return;
        }
        if (a % b == 0 || b % a == 0)
            yes;
        else
            no;
        return;
    }
    if (ans >= k)
        yes;
    else
        no;
}
int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int testcase = 1;
    cin >> testcase;
    for (int t = 1; t <= testcase; t++) {
        //cout << "Case #" << t << ": ";
        solve();
    }
#ifndef ONLINE_JUDGE
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
    return 0;
}

### 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
// ?-------------------------------------------------------------------------------------------------
// !                                         Shubham Lohan
// ?-------------------------------------------------------------------------------------------------

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

//! ------------------------------------------- Macros ----------------------------------------------

typedef long long ll;
typedef long double lld;

#define setbits(x) __builtin_popcountll(x)  // to count no of 1's
#define sp(x, y) fixed << setprecision(y) << x
#define flush fflush(stdout)
#define all(x) x.begin(), x.end()
#define nline "\n"
#define yes cout << "YES" << nline
#define no cout << "NO" << nline
#define vi vector<int>
#define mii map<int, int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define For(n) for (int i = 0; i < n; i++)
#define inf 1e9
const int MOD = 1e9 + 7;
//! ------------------------------------------ Debugger ---------------------------------------------

template <typename T>
void __print(const T &x);
void __print(const int &x) { cerr << x; }
void __print(const ll &x) { cerr << x; }
void __print(const lld &x) { cerr << x; }
void __print(const float &x) { cerr << x; }
void __print(const double &x) { cerr << x; }
void __print(const char &x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(const bool &x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) { cerr << '(', __print(x.first), cerr << ',', __print(x.second), cerr << ')'; }
template <typename T>
void __print(const T &x) {
    int c = 0;
    cerr << "{";
    for (auto i : x) cerr << (c++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define deb(x...)               \
    cerr << "[" << #x << ":  "; \
    _print(x)
#else
#define deb(x...)
#endif

//! ----------------------------------------- Algorithms --------------------------------------------

template <typename T, typename V>
float divide(T a, V b) { return (float)a / (float)b; }
bool isPrime(int n) {  //! time complexity O(sqrt(N))
    if (n <= 1)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}
vector<bool> sieve(int n) {
    vector<bool> prime(n + 1, true);
    prime[0] = false, prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= n; j += i)
                prime[j] = false;
        }
    }
    return prime;
}
vector<int> sieve_primeFactor(int n) {
    //! prime factorization using sieve
    vector<int> prime(n + 1);
    prime[1] = 1;
    for (int i = 2; i <= n; i++)
        prime[i] = i;
    for (int i = 4; i <= n; i += 2)
        prime[i] = 2;

    for (int i = 3; i * i <= n; i += 2) {
        if (prime[i] == i) {
            for (int j = i * i; j <= n; j += i) {
                if (prime[j] == j)
                    prime[j] = i;
            }
        }
    }
    return prime;
}
vector<int> prime_factor(int n, vector<int> &prime) {
    vector<int> factors;
    while (prime[n] != 1)
        factors.push_back(prime[n]), n = n / prime[n];
    if (n > 1) factors.push_back(n);
    return factors;
}
int phi(int n) {
    // ? finding Euler's totient function Φ(N) in O(sqrt(N)) time
    int result = n;
    if (n % 2 == 0) {
        result /= 2;
        while (n % 2 == 0)
            n /= 2;
    }
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result /= i, result *= (i - 1);
        }
    }
    if (n > 1)
        result /= n, result *= (n - 1);
    return result;
}
int power(int x, int n, int mod = MOD) {
    // ! used to calculate x^n in O(logn)
    int result = 1;
    while (n) {
        if (n & 1)  // odd
            result = (result * x) % mod, n--;
        x = (x * x) % mod, n = n >> 1;  // floor(n/2)
    }
    return result;
}
int modular_inverse(int x, int n) { return power(x, n - 2, n); }
vector<int> fact_mod(int n, int mod) {
    //? finding n! % mod
    vector<int> fact(n + 1);
    fact[0] = fact[1] = 1;
    for (int i = 2; i < fact.size(); i++)
        fact[i] = (fact[i - 1] * i) % mod;
    return fact;
}
int combination(int n, int k, const vector<int> &fact, int mod) {
    //! finding nCr % mod
    if (k > n)
        return 0;
    int result = fact[n];
    result = (result * modular_inverse(fact[k], mod)) % mod;
    result = (result * modular_inverse(fact[n - k], mod)) % mod;
    return result;
}
int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x1, y1;
    int d = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
int wheel(int n) {
    vector<int> factorization;
    int count = 0;
    for (int d : {2, 3, 5}) {
        while (n % d == 0) {
            // factorization.push_back(d);
            count++;
            n /= d;
        }
    }
    static array<int, 8> increments = {4, 2, 4, 2, 4, 6, 2, 6};
    int i = 0;
    for (int d = 7; d * d <= n; d += increments[i++]) {
        while (n % d == 0) {
            // factorization.push_back(d);
            count++;
            n /= d;
        }
        if (i == 8)
            i = 0;
    }
    if (n > 1) {
        // factorization.push_back(n);
        count++;
    }
    return count;
    // return factorization;
}
auto Compare = [](const int &a, const int &b) { return a > b; };

// !-------------------------------------------------------------------------------------------------
// ?                                           Solution
// !-------------------------------------------------------------------------------------------------

void solve() {
    int a, b, k;
    cin >> a >> b >> k;
    int ans = wheel(a);
    ans += wheel(b);

    if (k == 1) {
        if (a == b) {
            no;
            return;
        }
        if (a % b == 0 || b % a == 0)
            yes;
        else
            no;
        return;
    }
    if (ans >= k)
        yes;
    else
        no;
}
int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int testcase = 1;
    cin >> testcase;
    for (int t = 1; t <= testcase; t++) {
        //cout << "Case #" << t << ": ";
        solve();
    }
#ifndef ONLINE_JUDGE
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
    return 0;
}

```