#include<bits/stdc++.h>
using namespace  std;
 
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define ll           long long  
#define int          long long
#define vi           std::vector<int>
#define setbits(x)   __builtin_popcountll(x)
#define pb           push_back
#define fn           for(int i=0;i<n;i++)
#define rep(i,a,b)   for(int i=a;i<b;i++)
#define all(x)       x.begin(), x.end()
#define  ret(x) {cout << #x << endl; return;}
#define PI           3.14159265358979323846
#define deb(x) cout<<#x<<" = "<<x<<endl;
#define pii          pair<ll,ll>
#define fr           first
#define sc           second
 
// ar is vector of vector
// sort(ar.begin(), ar.end(), [](auto &a, auto &b) { return a[1] > b[1]; });
 
const int mod = 1e9+7;
void getio();
ll ceill(ll a, ll b) { return (a + b - 1) / b; }
 
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

const long long inf = 1e18;

vector<int> prime;

void solve() {
    int a, b, k;
    cin >> a >> b >> k;
    if(k==1) {
        if(a==b) {cout << "NO" << endl; return;}
        if((b>a and b%a==0) or (a>b and a%b==0)) {cout << "YES" << endl; return;}
    }

    // map<int, int> pa = primeFactorisation(a);
    // map<int, int> pb = primeFactorisation(b);
    // int cnt = 0;
    // for(auto i:pa) cnt += i.second;
    // for(auto i:pb) cnt += i.second;
    int mn = 0;
    if(a%b) mn++;
    if(b%a) mn++;
    if(k<mn) {cout << "NO" << endl; return;}

    int cnt = 0, pa = a, pb = b;
    for(int it=0; it<prime.size(); it++) {
        int i = prime[it];
        while(a%i==0) {cnt++; a/=i;}
        // a = pa;
        while(b%i==0) {cnt++; b/=i;}
        // b = pb;
    }
    if(a>1) cnt++;
    if(b>1) cnt++;

    if(k<=cnt) cout << "YES";
    else cout << "NO";
    cout << endl;
}

bool check_prime(int n)
{
    for (int i = 2; i*i<=n; i++) if(n%i==0) return false;
    return true;
}

int32_t main()
{   
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    getio();
    for(int i=2; i*i<1e9; i++) {
        if(check_prime(i)) prime.pb(i);
    }
    int t; cin>> t; while(t--) 
    solve();
}
 
void getio()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

### Prompt

Create a solution in CPP for 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;
 
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define ll           long long  
#define int          long long
#define vi           std::vector<int>
#define setbits(x)   __builtin_popcountll(x)
#define pb           push_back
#define fn           for(int i=0;i<n;i++)
#define rep(i,a,b)   for(int i=a;i<b;i++)
#define all(x)       x.begin(), x.end()
#define  ret(x) {cout << #x << endl; return;}
#define PI           3.14159265358979323846
#define deb(x) cout<<#x<<" = "<<x<<endl;
#define pii          pair<ll,ll>
#define fr           first
#define sc           second
 
// ar is vector of vector
// sort(ar.begin(), ar.end(), [](auto &a, auto &b) { return a[1] > b[1]; });
 
const int mod = 1e9+7;
void getio();
ll ceill(ll a, ll b) { return (a + b - 1) / b; }
 
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

const long long inf = 1e18;

vector<int> prime;

void solve() {
    int a, b, k;
    cin >> a >> b >> k;
    if(k==1) {
        if(a==b) {cout << "NO" << endl; return;}
        if((b>a and b%a==0) or (a>b and a%b==0)) {cout << "YES" << endl; return;}
    }

    // map<int, int> pa = primeFactorisation(a);
    // map<int, int> pb = primeFactorisation(b);
    // int cnt = 0;
    // for(auto i:pa) cnt += i.second;
    // for(auto i:pb) cnt += i.second;
    int mn = 0;
    if(a%b) mn++;
    if(b%a) mn++;
    if(k<mn) {cout << "NO" << endl; return;}

    int cnt = 0, pa = a, pb = b;
    for(int it=0; it<prime.size(); it++) {
        int i = prime[it];
        while(a%i==0) {cnt++; a/=i;}
        // a = pa;
        while(b%i==0) {cnt++; b/=i;}
        // b = pb;
    }
    if(a>1) cnt++;
    if(b>1) cnt++;

    if(k<=cnt) cout << "YES";
    else cout << "NO";
    cout << endl;
}

bool check_prime(int n)
{
    for (int i = 2; i*i<=n; i++) if(n%i==0) return false;
    return true;
}

int32_t main()
{   
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    getio();
    for(int i=2; i*i<1e9; i++) {
        if(check_prime(i)) prime.pb(i);
    }
    int t; cin>> t; while(t--) 
    solve();
}
 
void getio()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

```