#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define oo 1000000000
#define MOD 1000000007
#define fast ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define test ll TT;cin>>TT;for(ll hhh=1;hhh<=TT;hhh++)
#define test1 ll TT;TT=1;for(ll hhh=1;hhh<=TT;hhh++)
#define asd cout<<"ans= "
#define B break
#define C continue


ll a,b,k;

ll bs[100100];
vector <ll> prims;
void sieve(ll nn)
{
    bs[0]=0;
    bs[1]=0;
    for(ll i=2;i<nn;i++)
        if(bs[i]==0)
        {
             prims.push_back(i);
             for(int j=i*i;j<nn;j+=i) bs[j]=1;
        }
}

ll f(ll N)
{
     ll ans=0;
     ll PF_idx=0;
     ll pf=prims[PF_idx];
     while(pf*pf<=N)
     {
         while(N%pf==0) {N/=pf; ans++; }
         PF_idx++;
         pf=prims[PF_idx];
     }
     if(N!=1)ans++;
     return ans;
}



int main()
{
fast;
//freopen("test.txt","r",stdin);
sieve(33000);
test
{
    cin>>a>>b>>k;
    //asd;

    if(k>60)
    {
        cout<<"NO"<<endl;
        C;
    }

    if( a==1 && b==1 )
    {
        cout<<"NO"<<endl;
        C;
    }
    if( k==1 )
    {
        ll mx=max(a,b);
        ll mn=min(a,b);

        if(mx==mn)
        {
            cout<<"NO"<<endl;
            C;
        }

        if(mx%mn==0)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
        C;
    }
    ll na=f(a);
    ll nb=f(b);

    if( na+nb==1 )
    {
        if(k>1)
        {
            cout<<"NO"<<endl;
        }
        else
        {
            cout<<"YES"<<endl;
        }
        C;
    }

    if( k<=na+nb )
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }

}
}

### 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;
#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define oo 1000000000
#define MOD 1000000007
#define fast ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define test ll TT;cin>>TT;for(ll hhh=1;hhh<=TT;hhh++)
#define test1 ll TT;TT=1;for(ll hhh=1;hhh<=TT;hhh++)
#define asd cout<<"ans= "
#define B break
#define C continue


ll a,b,k;

ll bs[100100];
vector <ll> prims;
void sieve(ll nn)
{
    bs[0]=0;
    bs[1]=0;
    for(ll i=2;i<nn;i++)
        if(bs[i]==0)
        {
             prims.push_back(i);
             for(int j=i*i;j<nn;j+=i) bs[j]=1;
        }
}

ll f(ll N)
{
     ll ans=0;
     ll PF_idx=0;
     ll pf=prims[PF_idx];
     while(pf*pf<=N)
     {
         while(N%pf==0) {N/=pf; ans++; }
         PF_idx++;
         pf=prims[PF_idx];
     }
     if(N!=1)ans++;
     return ans;
}



int main()
{
fast;
//freopen("test.txt","r",stdin);
sieve(33000);
test
{
    cin>>a>>b>>k;
    //asd;

    if(k>60)
    {
        cout<<"NO"<<endl;
        C;
    }

    if( a==1 && b==1 )
    {
        cout<<"NO"<<endl;
        C;
    }
    if( k==1 )
    {
        ll mx=max(a,b);
        ll mn=min(a,b);

        if(mx==mn)
        {
            cout<<"NO"<<endl;
            C;
        }

        if(mx%mn==0)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
        C;
    }
    ll na=f(a);
    ll nb=f(b);

    if( na+nb==1 )
    {
        if(k>1)
        {
            cout<<"NO"<<endl;
        }
        else
        {
            cout<<"YES"<<endl;
        }
        C;
    }

    if( k<=na+nb )
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }

}
}

```