#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int , int> pi;
typedef pair<long long,long long> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;


#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int MAX=2e5+35;
const ll mod=1e9+7;
const double eps=1e-6;
using namespace std;
ll N=1e5;
bool pri[MAX];
vll pr;
ll a[MAX];
ll f(ll x)
{
    ll s=0;
    for (ll i=0;pr[i]*pr[i]<=x;i++)
    {
        while(x%pr[i]==0)
        {
            x/=pr[i];
            s++;
        }
    }
    if (x>1)
        s++;
    return s;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    int t;
    cin>>t;
    for (int i=2;i<=N;i++)
    {
        if (pri[i]==0)
        {
            pr.pb(i);
            for (int j=i+i;j<=N;j+=i)
                pri[j]=1;
        }
    }
    while(t--)
    {
        ll a,k,b;
        cin>>a>>b>>k;
        if (a>b)
            swap(a,b);
        ll a1=f(a);
        ll b1=f(b);
        if (a==1)
        {
            if (b==a)
            {
                cout<<"NO\n";
                continue;
            }
            if (b1>=k)
                cout<<"YES\n";
            else
                cout<<"NO\n";
            continue;
        }
        if (k==1)
        {
            if (b%a==0&&b/a!=1)
            {
                cout<<"YES\n";
                continue;
            }
            cout<<"NO\n";
            continue;
        }
        if (a1+b1>=k)
        {
            cout<<"YES\n";
            continue;
        }
        cout<<"NO\n";
    }
    return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
typedef long long ll;
typedef pair<int , int> pi;
typedef pair<long long,long long> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;


#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int MAX=2e5+35;
const ll mod=1e9+7;
const double eps=1e-6;
using namespace std;
ll N=1e5;
bool pri[MAX];
vll pr;
ll a[MAX];
ll f(ll x)
{
    ll s=0;
    for (ll i=0;pr[i]*pr[i]<=x;i++)
    {
        while(x%pr[i]==0)
        {
            x/=pr[i];
            s++;
        }
    }
    if (x>1)
        s++;
    return s;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    int t;
    cin>>t;
    for (int i=2;i<=N;i++)
    {
        if (pri[i]==0)
        {
            pr.pb(i);
            for (int j=i+i;j<=N;j+=i)
                pri[j]=1;
        }
    }
    while(t--)
    {
        ll a,k,b;
        cin>>a>>b>>k;
        if (a>b)
            swap(a,b);
        ll a1=f(a);
        ll b1=f(b);
        if (a==1)
        {
            if (b==a)
            {
                cout<<"NO\n";
                continue;
            }
            if (b1>=k)
                cout<<"YES\n";
            else
                cout<<"NO\n";
            continue;
        }
        if (k==1)
        {
            if (b%a==0&&b/a!=1)
            {
                cout<<"YES\n";
                continue;
            }
            cout<<"NO\n";
            continue;
        }
        if (a1+b1>=k)
        {
            cout<<"YES\n";
            continue;
        }
        cout<<"NO\n";
    }
    return 0;
}

```