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

#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define fo(i, k, n) for(int i = k; i < n; ++i)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
void setIO(string name = "") { 
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(name.size()){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

const int mod = 1e9 + 7, mxX = 1e3, mxN = 1e5;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main()
{	
    setIO();
    int t;
    cin >> t;
    while(t--){
        int a, b, k;
        cin >> a >> b >> k;

        if(a > b) swap(a, b);
        if(a == 1 && b == 1) {
            cout << "No" << endl;
            continue;
        }
        
        int ul;

        
        if(b % a == 0 && a != b) ul = 1;
        else ul = 2;
        

        int expos1 = 0, expos2 = 0;

        for(int i = 2; i * i <= a; ++i) {
            
            if(a % i == 0) {
                while (a % i == 0) {
                    expos1++;
                    a /= i;
                }
            }

        }
        if(a > 1) expos1++;

        for(int i = 2; i * i <= b; ++i) {
            
            if(b % i == 0) {
                while (b % i == 0) {
                    expos2++;
                    b /= i;
                }
            }

        }
        if(b > 1) expos2++;

        int tl = expos1 + expos2;

        if(ul <= k && k <= tl) cout << "Yes" << endl;
        else cout << "No" << endl;

    }
    return 0;
}

### Prompt

Please create a solution in CPP 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;

#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define fo(i, k, n) for(int i = k; i < n; ++i)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
void setIO(string name = "") { 
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(name.size()){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

const int mod = 1e9 + 7, mxX = 1e3, mxN = 1e5;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main()
{	
    setIO();
    int t;
    cin >> t;
    while(t--){
        int a, b, k;
        cin >> a >> b >> k;

        if(a > b) swap(a, b);
        if(a == 1 && b == 1) {
            cout << "No" << endl;
            continue;
        }
        
        int ul;

        
        if(b % a == 0 && a != b) ul = 1;
        else ul = 2;
        

        int expos1 = 0, expos2 = 0;

        for(int i = 2; i * i <= a; ++i) {
            
            if(a % i == 0) {
                while (a % i == 0) {
                    expos1++;
                    a /= i;
                }
            }

        }
        if(a > 1) expos1++;

        for(int i = 2; i * i <= b; ++i) {
            
            if(b % i == 0) {
                while (b % i == 0) {
                    expos2++;
                    b /= i;
                }
            }

        }
        if(b > 1) expos2++;

        int tl = expos1 + expos2;

        if(ul <= k && k <= tl) cout << "Yes" << endl;
        else cout << "No" << endl;

    }
    return 0;
}

```