#include <bits/stdc++.h>
using namespace std;

int n_prime_divs(const vector<int>& primes, int a) {
    int res = 0;
    for(const auto& x : primes) {
        while(a%x == 0) {
            a /= x;
            ++res;
        }

        if(a == 1) {
            break;
        }
    }

    return (a == 1) ? res : (res+1);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t, a, b, k;
    cin >> t;

    int N = 32000;
    vector<int> primes;
    vector<bool> numbers(N+1, true);
    numbers[0] = false;
    numbers[1] = false;

    for(int i=2; i<=N; i++) {
        if(numbers[i]) {
            primes.push_back(i);
            for(int j=2*i; j<=N; j+=i) {
                numbers[j] = false;
            }
        }
    }
/*
    for(const auto& x : primes) {
        cout << x << " ";
    }
*/
    while(t--) {
        cin >> a >> b >> k;
        if (a > b) swap(a, b);

        if (k == 1) {
            if (a == b) {
                cout << "NO\n";
            } else {
                if (a == 1 || b == 1) {
                    cout << "YES\n";
                    continue;
                }
                if (b%a == 0) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            }
        } else {
            int a_divs = n_prime_divs(primes, a);
            int b_divs = n_prime_divs(primes, b);
            if (k > a_divs + b_divs) {
                cout << "NO\n";
            } else {
                cout << "YES\n";
            }
        }
    }

    return 0;
}

### Prompt

Please provide a Cpp coded solution 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
#include <bits/stdc++.h>
using namespace std;

int n_prime_divs(const vector<int>& primes, int a) {
    int res = 0;
    for(const auto& x : primes) {
        while(a%x == 0) {
            a /= x;
            ++res;
        }

        if(a == 1) {
            break;
        }
    }

    return (a == 1) ? res : (res+1);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t, a, b, k;
    cin >> t;

    int N = 32000;
    vector<int> primes;
    vector<bool> numbers(N+1, true);
    numbers[0] = false;
    numbers[1] = false;

    for(int i=2; i<=N; i++) {
        if(numbers[i]) {
            primes.push_back(i);
            for(int j=2*i; j<=N; j+=i) {
                numbers[j] = false;
            }
        }
    }
/*
    for(const auto& x : primes) {
        cout << x << " ";
    }
*/
    while(t--) {
        cin >> a >> b >> k;
        if (a > b) swap(a, b);

        if (k == 1) {
            if (a == b) {
                cout << "NO\n";
            } else {
                if (a == 1 || b == 1) {
                    cout << "YES\n";
                    continue;
                }
                if (b%a == 0) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            }
        } else {
            int a_divs = n_prime_divs(primes, a);
            int b_divs = n_prime_divs(primes, b);
            if (k > a_divs + b_divs) {
                cout << "NO\n";
            } else {
                cout << "YES\n";
            }
        }
    }

    return 0;
}

```