#include "bits/stdc++.h"

using namespace std;

void __print(int x) { cerr << x; }

void __print(long long x) { cerr << x; }

void __print(unsigned long long x) { cerr << x; }

void __print(long double x) { cerr << x; }

void __print(char x) { cerr << x; }

void __print(const char *x) { cerr << x; }

void __print(const string &x) { cerr << x; }

void __print(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 f = 0;
    cerr << '{';
    for (auto &i : x) {
        cerr << (f++ ? ", " : "");
        __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 dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define  dbg(x...)
#endif

#define int long long
#define endl '\n'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(X) (X).begin(), (X).end()
#define allr(X) (X).rbegin(), (X).rend()
#define sz(X) (int)X.size()
#define setbits(X) __builtin_popcountll(X)
#define fix(X) fixed << setprecision(X)
#define mem0(X) memset((X), 0, sizeof((X)))
#define mem1(X) memset((X), -1, sizeof((X)))

vector<int> primes;

void sieve() {
    int n = 1e5;
    vector<bool> prime(n + 1, true);
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            primes.pb(p);
        }
    }
}

void solve() {
    int a, b, k;
    cin >> a >> b >> k;
    auto go = [&](int x) -> int {
        int cnt = 0;
        for (auto i: primes) {
            if (x % i) {
                continue;
            }
            if (i > x) {
                break;
            }
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
        }
        cnt += (x > 1);
        return cnt;
    };
    int sum = go(a) + go(b);
    dbg(sum, a, b);
    if (k == 1) {
        if (a == b) {
            cout << "NO" << endl;
        } else if (a % b == 0 || b % a == 0) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
        return;
    }
    if (sum >= k) {
        cout << "YES" << endl;
        return;
    }
    cout << "NO" << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    sieve();
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}
### Prompt

Please formulate 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"

using namespace std;

void __print(int x) { cerr << x; }

void __print(long long x) { cerr << x; }

void __print(unsigned long long x) { cerr << x; }

void __print(long double x) { cerr << x; }

void __print(char x) { cerr << x; }

void __print(const char *x) { cerr << x; }

void __print(const string &x) { cerr << x; }

void __print(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 f = 0;
    cerr << '{';
    for (auto &i : x) {
        cerr << (f++ ? ", " : "");
        __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 dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define  dbg(x...)
#endif

#define int long long
#define endl '\n'
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(X) (X).begin(), (X).end()
#define allr(X) (X).rbegin(), (X).rend()
#define sz(X) (int)X.size()
#define setbits(X) __builtin_popcountll(X)
#define fix(X) fixed << setprecision(X)
#define mem0(X) memset((X), 0, sizeof((X)))
#define mem1(X) memset((X), -1, sizeof((X)))

vector<int> primes;

void sieve() {
    int n = 1e5;
    vector<bool> prime(n + 1, true);
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            primes.pb(p);
        }
    }
}

void solve() {
    int a, b, k;
    cin >> a >> b >> k;
    auto go = [&](int x) -> int {
        int cnt = 0;
        for (auto i: primes) {
            if (x % i) {
                continue;
            }
            if (i > x) {
                break;
            }
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
        }
        cnt += (x > 1);
        return cnt;
    };
    int sum = go(a) + go(b);
    dbg(sum, a, b);
    if (k == 1) {
        if (a == b) {
            cout << "NO" << endl;
        } else if (a % b == 0 || b % a == 0) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
        return;
    }
    if (sum >= k) {
        cout << "YES" << endl;
        return;
    }
    cout << "NO" << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    sieve();
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}
```