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

const int N = 4e4 + 17;
int prime[N], vis[N];

void init(){
    for(int i = 2; i < N; ++i){
        if(!vis[i]) prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0]; ++j){
            if(i * prime[j] >= N) break;
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

void solve(){
    int a, b, k;
    cin >> a >> b >> k;
    int aa = a, bb = b, k0 = 0, k1 = 0, k2 = 0;
    for(int i = 1; i <= prime[0] && prime[i] <= min(aa, bb); ++i){
        int pr = prime[i];
        while(aa % pr == 0 && bb % pr == 0){
            aa /= pr;
            bb /= pr;
            k0++;
        }
    }
    
    for(int i = 1; i <= prime[0] && prime[i] <= aa; ++i){
        int pr = prime[i];
        while(aa % pr == 0){
            aa /= pr;
            k1++;
        }
    }

    for(int i = 1; i <= prime[0] && prime[i] <= bb; ++i){
        int pr = prime[i];
        while(bb % pr == 0){
            bb /= pr;
            k2++;
        }
    }
    if(aa == bb && aa > 1) {
        k0++;
        aa = 1, bb = 1;
    }
    if(aa > 1) k1++;
    if(bb > 1) k2++;

    //cout << k0 << ' ' << k1 << ' ' << k2 << endl;

    if(k == 1 && ((k1 && k2) || k1 + k2 == 0)){
        cout << "No" << endl;
        return;
    }
    if(k1 + k2 + 2 * k0 < k){
        cout << "No" << endl;
        return;
    }
    cout << "Yes" << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
### Prompt

Your challenge is to write 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;
#define int long long

const int N = 4e4 + 17;
int prime[N], vis[N];

void init(){
    for(int i = 2; i < N; ++i){
        if(!vis[i]) prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0]; ++j){
            if(i * prime[j] >= N) break;
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

void solve(){
    int a, b, k;
    cin >> a >> b >> k;
    int aa = a, bb = b, k0 = 0, k1 = 0, k2 = 0;
    for(int i = 1; i <= prime[0] && prime[i] <= min(aa, bb); ++i){
        int pr = prime[i];
        while(aa % pr == 0 && bb % pr == 0){
            aa /= pr;
            bb /= pr;
            k0++;
        }
    }
    
    for(int i = 1; i <= prime[0] && prime[i] <= aa; ++i){
        int pr = prime[i];
        while(aa % pr == 0){
            aa /= pr;
            k1++;
        }
    }

    for(int i = 1; i <= prime[0] && prime[i] <= bb; ++i){
        int pr = prime[i];
        while(bb % pr == 0){
            bb /= pr;
            k2++;
        }
    }
    if(aa == bb && aa > 1) {
        k0++;
        aa = 1, bb = 1;
    }
    if(aa > 1) k1++;
    if(bb > 1) k2++;

    //cout << k0 << ' ' << k1 << ' ' << k2 << endl;

    if(k == 1 && ((k1 && k2) || k1 + k2 == 0)){
        cout << "No" << endl;
        return;
    }
    if(k1 + k2 + 2 * k0 < k){
        cout << "No" << endl;
        return;
    }
    cout << "Yes" << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
```