#include<iostream>
#include<vector>
#include<stack>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<tuple>
#include<bitset>
#include<queue>
#include<random>
using namespace std;
void BoostIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
//#define int long long
#define ff first
#define ss second
#define fori(n)  for(int i = 0; i < (n); ++i)
#define forj(n)  for(int j = 0; j < (n); ++j)
typedef long long ll;
typedef unsigned long long ull;
int const maxn = 100005;
double pi = 3.1415926535897932;
double eps = 1e-7;
/*int Pow(int a, int b) {
    if (b == 0) {
        return 1;
    }
    int v = Pow(a, b / 2);
    if (b % 2 == 0) {
        return v * v;
    }
    else {
        return v * v * a;
    }
}
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    a = a % b;
    gcd(b, a);
}
int f(int a) {
    return a * (a + 1) / 2;
}*/
int32_t main() {
    BoostIO();
    int T;
    cin >> T;
    while (T--) {
        int a, b, k;
        cin >> a >> b >> k;
        if (k == 1) {
            if ((a % b == 0 || b % a == 0) && a != b) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
            }
            continue;
        }
        /*if (k == 2) {
            if (a != 1 && b != 1) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
            }
            continue;
        }*/
        int cnt1=0;
        int cnt2=0;
        int a1 = a;
        int b1 = b;

        for (int i = 2; i * i <= a; ++i) {
            if (a1 == 1) {
                break;
            }
            while (a1 % i == 0) {
                ++cnt1;
                a1 /= i;
            }
        }
        if (a1 != 1) {
            ++cnt1;
        }
        
        for (int i = 2; i * i <= b; ++i) {
            if (b1 == 1) {
                break;
            }
            while (b1 % i == 0) {
                ++cnt2;
                b1 /= i;
            }
        }
        if (b1 != 1) {
            ++cnt2;
        }
       // cout << cnt1 << ' ' << cnt2 << endl;
        if (cnt1 + cnt2 >= k) {
            cout << "YES" << endl;
        }
        else {
            cout<<"NO"<<endl;
        }

    }
}
### 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<iostream>
#include<vector>
#include<stack>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<tuple>
#include<bitset>
#include<queue>
#include<random>
using namespace std;
void BoostIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
//#define int long long
#define ff first
#define ss second
#define fori(n)  for(int i = 0; i < (n); ++i)
#define forj(n)  for(int j = 0; j < (n); ++j)
typedef long long ll;
typedef unsigned long long ull;
int const maxn = 100005;
double pi = 3.1415926535897932;
double eps = 1e-7;
/*int Pow(int a, int b) {
    if (b == 0) {
        return 1;
    }
    int v = Pow(a, b / 2);
    if (b % 2 == 0) {
        return v * v;
    }
    else {
        return v * v * a;
    }
}
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    a = a % b;
    gcd(b, a);
}
int f(int a) {
    return a * (a + 1) / 2;
}*/
int32_t main() {
    BoostIO();
    int T;
    cin >> T;
    while (T--) {
        int a, b, k;
        cin >> a >> b >> k;
        if (k == 1) {
            if ((a % b == 0 || b % a == 0) && a != b) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
            }
            continue;
        }
        /*if (k == 2) {
            if (a != 1 && b != 1) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
            }
            continue;
        }*/
        int cnt1=0;
        int cnt2=0;
        int a1 = a;
        int b1 = b;

        for (int i = 2; i * i <= a; ++i) {
            if (a1 == 1) {
                break;
            }
            while (a1 % i == 0) {
                ++cnt1;
                a1 /= i;
            }
        }
        if (a1 != 1) {
            ++cnt1;
        }
        
        for (int i = 2; i * i <= b; ++i) {
            if (b1 == 1) {
                break;
            }
            while (b1 % i == 0) {
                ++cnt2;
                b1 /= i;
            }
        }
        if (b1 != 1) {
            ++cnt2;
        }
       // cout << cnt1 << ' ' << cnt2 << endl;
        if (cnt1 + cnt2 >= k) {
            cout << "YES" << endl;
        }
        else {
            cout<<"NO"<<endl;
        }

    }
}
```