/*     Hare Krishna............Har Har Mahadev    */
//cin.ignore();getline(cin,s,'\n');
#include <bits/stdc++.h>
using namespace std; 
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define lab(i,a,b) for(i=a;i<=b;i++)
#define bal(i,a,b) for(i=b;i>=a;i--)
#define ff first 
#define ss second 
#define pb push_back
#define se(v) v.begin(), v.end()
#define fst ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define tc ll t;cin>>t;while(t--) 
#define fceil(a,b) ceil((ld)a/(ld)b)
#define dis(v) for(auto it:v)cout<<it<<" "
#define yep cout<<"YES\n"
#define nope cout<<"NO\n"
const int limit=100000;
vector<int> v;bool mark[limit+1];
//bool isPrime(int n){if(n <= 1)return false;if(n <= 3)return true;if(n%2==0||n%3==0)return false;for(ll i=5;i*i<= n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
void simpleSieve()
{
    int i;
    memset(mark, true, sizeof(mark));
    for (int p=2; p*p<=limit; p++)
    {
        if (mark[p] == true)
        {
            //v.pb(p);
            for (int i=p*p; i<=limit; i+=p)
                mark[i] = false;
        }
    }
    lab(i,2,limit-1)if(mark[i])v.pb(i);
}
const ll MOD = 1e9 + 7;
//ll powerLL(ll x, ll n){ll result = 1;while (n){if (n & 1)result = result * x % MOD;n = n / 2;x = x * x % MOD;}return result;}
int main() 
{ 
    fst
    simpleSieve();
    int n,m,i,j,k,f,x,y,z,ans;
    tc
    {
      m=0,i=0,j=0,f=0,x=0,y=0,z=0,ans=0;
      cin>>x>>y>>k;
      m=x;n=y;
      for(auto it:v)
      {
          if(x==1)break;
           //dis(v);
          while(x%it==0)
          {
              x=x/it;
              f++;
          }
         
      }
      
      for(auto it:v)
      {
          //dis(v);
          if(y==1)break;
          while(y%it==0)
          {
              y=y/it;
              f++;
          }
          
      }
      if(x!=1)
      f++;
      if(y!=1)
      f++;
      //dis(v);
      //cout<<f<<"\n";
      if(m>n)swap(m,n);
      if(n!=m && n%m==0 && k==1)yep;
      else if(k>=2 && k<=f)yep;
      else nope;
    }
    return 0; 
} 
### Prompt

Create a solution in cpp for 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
/*     Hare Krishna............Har Har Mahadev    */
//cin.ignore();getline(cin,s,'\n');
#include <bits/stdc++.h>
using namespace std; 
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define lab(i,a,b) for(i=a;i<=b;i++)
#define bal(i,a,b) for(i=b;i>=a;i--)
#define ff first 
#define ss second 
#define pb push_back
#define se(v) v.begin(), v.end()
#define fst ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define tc ll t;cin>>t;while(t--) 
#define fceil(a,b) ceil((ld)a/(ld)b)
#define dis(v) for(auto it:v)cout<<it<<" "
#define yep cout<<"YES\n"
#define nope cout<<"NO\n"
const int limit=100000;
vector<int> v;bool mark[limit+1];
//bool isPrime(int n){if(n <= 1)return false;if(n <= 3)return true;if(n%2==0||n%3==0)return false;for(ll i=5;i*i<= n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
void simpleSieve()
{
    int i;
    memset(mark, true, sizeof(mark));
    for (int p=2; p*p<=limit; p++)
    {
        if (mark[p] == true)
        {
            //v.pb(p);
            for (int i=p*p; i<=limit; i+=p)
                mark[i] = false;
        }
    }
    lab(i,2,limit-1)if(mark[i])v.pb(i);
}
const ll MOD = 1e9 + 7;
//ll powerLL(ll x, ll n){ll result = 1;while (n){if (n & 1)result = result * x % MOD;n = n / 2;x = x * x % MOD;}return result;}
int main() 
{ 
    fst
    simpleSieve();
    int n,m,i,j,k,f,x,y,z,ans;
    tc
    {
      m=0,i=0,j=0,f=0,x=0,y=0,z=0,ans=0;
      cin>>x>>y>>k;
      m=x;n=y;
      for(auto it:v)
      {
          if(x==1)break;
           //dis(v);
          while(x%it==0)
          {
              x=x/it;
              f++;
          }
         
      }
      
      for(auto it:v)
      {
          //dis(v);
          if(y==1)break;
          while(y%it==0)
          {
              y=y/it;
              f++;
          }
          
      }
      if(x!=1)
      f++;
      if(y!=1)
      f++;
      //dis(v);
      //cout<<f<<"\n";
      if(m>n)swap(m,n);
      if(n!=m && n%m==0 && k==1)yep;
      else if(k>=2 && k<=f)yep;
      else nope;
    }
    return 0; 
} 
```