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

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << x;}
void __print(const char *x) {cerr << x;}
void __print(const string &x) {cerr << x;}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first); cerr << ", "; __print(x.second);
    cerr << '}';
}
 
template<typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
    {
        cerr << (f++ ? ", " : "");
        __print(i);
    }
    cerr << "}";
}
void _print()
{
    cerr << "]\n";
}
 
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
    {
        cerr << ", ";
    }
    _print(v...);
}
 
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define  dbg(x...)
#endif
 
 
#define ll              long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define pii_l           pair<long long,long long>
#define vi              vector<int>
#define vi_l            vector<long long>
#define mii             map<int,int>
#define mii_l           map<long long,long long>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e9
#define n_inf            -1e9
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define floop(x,a,b)    for(int x = a; x < b; x++)
#define rloop(x,a,b)    for(int x = a; x > b; x--)
#define FIO             ios_base::sync_with_stdio(false);cin.tie(NULL);
 
 
 
int main(void)
{
 
    FIO
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif    
    w(t){
        int a,b,k;cin>>a>>b>>k;
        int x = 0;
        if(k == 1){
            if(a != b && max(a,b)%min(a,b) == 0){
                cout << "YES" << endl;
            }
            else{
                cout << "NO" << endl;
            }
            continue;
        }

        for(int i = 2; i*i <= max(a,b); i++){
            while(a%i == 0){
                a = a/i;
                x++;
                if(x >= k){
                    break;
                }
            }
            while(b%i == 0){
                b = b/i;
                x++;
                if(x >= k){
                    break;
                }
            }
            if(x >= k){
                    break;
            }
        }
        if(a > 1){
            x++;
        }
        if(b > 1){
            x++;
        }

        if(x >= k){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }

    return 0;
}






















### Prompt

Your task is to create 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; 

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << x;}
void __print(const char *x) {cerr << x;}
void __print(const string &x) {cerr << x;}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first); cerr << ", "; __print(x.second);
    cerr << '}';
}
 
template<typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
    {
        cerr << (f++ ? ", " : "");
        __print(i);
    }
    cerr << "}";
}
void _print()
{
    cerr << "]\n";
}
 
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
    {
        cerr << ", ";
    }
    _print(v...);
}
 
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define  dbg(x...)
#endif
 
 
#define ll              long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define pii_l           pair<long long,long long>
#define vi              vector<int>
#define vi_l            vector<long long>
#define mii             map<int,int>
#define mii_l           map<long long,long long>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e9
#define n_inf            -1e9
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define floop(x,a,b)    for(int x = a; x < b; x++)
#define rloop(x,a,b)    for(int x = a; x > b; x--)
#define FIO             ios_base::sync_with_stdio(false);cin.tie(NULL);
 
 
 
int main(void)
{
 
    FIO
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif    
    w(t){
        int a,b,k;cin>>a>>b>>k;
        int x = 0;
        if(k == 1){
            if(a != b && max(a,b)%min(a,b) == 0){
                cout << "YES" << endl;
            }
            else{
                cout << "NO" << endl;
            }
            continue;
        }

        for(int i = 2; i*i <= max(a,b); i++){
            while(a%i == 0){
                a = a/i;
                x++;
                if(x >= k){
                    break;
                }
            }
            while(b%i == 0){
                b = b/i;
                x++;
                if(x >= k){
                    break;
                }
            }
            if(x >= k){
                    break;
            }
        }
        if(a > 1){
            x++;
        }
        if(b > 1){
            x++;
        }

        if(x >= k){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }

    return 0;
}






















```