#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define int long long int
#define pii pair<int,int>
const int INF= 2e18;
const int MAX=1e5+5;
const int MAXK=20;
const int mod = 1e9+7;
int gcd(int a, int b)
{
    while(b!=0)
    {
        a=a%b;
        swap(a,b);
    }
    return a;
}
int binpow(int a,int b)
{
    int res=1;
    while(b>0)
    {
        if(b%2==1)
            res=res*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return res%mod;
}
vector<int> prime;
bool vis[MAX];
void sieve()
{
    memset(vis,false,sizeof(vis));
    vis[1]=vis[0]=true;
    for(int i=0;i*i<=MAX;i++){
        if(!vis[i])
        {
            for(int j=i*i;j<MAX;j+=i)
            {
                vis[j]=true;
            }
        }
    }
    for(int i=2;i<MAX;i++)
    {
        if(!vis[i])
            prime.pb(i);
    }
}
void solve()
{
    int a,b,k;
    cin>>a>>b>>k;
    if(k==1)
    {
        if(a==b)
        {
            cout<<"NO\n";
        }
        else if(a%b==0||b%a==0)
        {
            cout<<"YES\n";
        }
        else
        {
            cout<<"NO\n";
        }
        return;
    }
    int one=0,two=0;
    for(auto u:prime)
    {
        if(u*u>a)
            break;
        while(a%u==0)
        {
            one++;
            a/=u;
        }
    }
    if(a>1)
    {
        one++;
    }
    for(auto u:prime)
    {
        if(u*u>b)
            break;
        while(b%u==0)
        {
            two++;
            b/=u;
        }
    }
    if(b>1)
    {
        two++;
    }
    if(one+two<k)
    {
        cout<<"NO\n";
    }
    else
    {
        cout<<"YES\n";
    }

}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif // ONLINE_JUDGE
    int t=1;
    cin>>t;
    sieve();
    for(int i=1;i<=t;i++)
    {
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}
### Prompt

Please formulate 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 pb push_back
#define fi first
#define se second
#define int long long int
#define pii pair<int,int>
const int INF= 2e18;
const int MAX=1e5+5;
const int MAXK=20;
const int mod = 1e9+7;
int gcd(int a, int b)
{
    while(b!=0)
    {
        a=a%b;
        swap(a,b);
    }
    return a;
}
int binpow(int a,int b)
{
    int res=1;
    while(b>0)
    {
        if(b%2==1)
            res=res*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return res%mod;
}
vector<int> prime;
bool vis[MAX];
void sieve()
{
    memset(vis,false,sizeof(vis));
    vis[1]=vis[0]=true;
    for(int i=0;i*i<=MAX;i++){
        if(!vis[i])
        {
            for(int j=i*i;j<MAX;j+=i)
            {
                vis[j]=true;
            }
        }
    }
    for(int i=2;i<MAX;i++)
    {
        if(!vis[i])
            prime.pb(i);
    }
}
void solve()
{
    int a,b,k;
    cin>>a>>b>>k;
    if(k==1)
    {
        if(a==b)
        {
            cout<<"NO\n";
        }
        else if(a%b==0||b%a==0)
        {
            cout<<"YES\n";
        }
        else
        {
            cout<<"NO\n";
        }
        return;
    }
    int one=0,two=0;
    for(auto u:prime)
    {
        if(u*u>a)
            break;
        while(a%u==0)
        {
            one++;
            a/=u;
        }
    }
    if(a>1)
    {
        one++;
    }
    for(auto u:prime)
    {
        if(u*u>b)
            break;
        while(b%u==0)
        {
            two++;
            b/=u;
        }
    }
    if(b>1)
    {
        two++;
    }
    if(one+two<k)
    {
        cout<<"NO\n";
    }
    else
    {
        cout<<"YES\n";
    }

}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif // ONLINE_JUDGE
    int t=1;
    cin>>t;
    sieve();
    for(int i=1;i<=t;i++)
    {
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}
```