#include<bits/stdc++.h>
#define ll long long int
#define loop(i,k,n) for (ll i = k; i <= n; i++) 
#define rloop(i,k,n) for (ll i = k; i >= n; i--)
#define INF 100000000000
#define umap unordered_map
#define mii map<int,int>
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define pqMin priority_queue<int,vector<int>,greater<int>>
#define pqMax priority_queue<int>
#define pqpii priority_queue<pii>
#define mll map<ll,ll>
#define pll pair<ll,ll>
#define vl vector<ll>
#define vvl vector<vl>
#define vpll vector<pll>
#define ft first 
#define st second                       
#define pb push_back  
#define pob pop_back 
#define mp make_pair 
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define gcd(a,b) __gcd((a),(b))
#define bitcnt(a) __builtin_popcount(a)
#define filla(a, b) memset(a, b, sizeof(a))
#define tc() ll t; cin>>t;while(t--)
#define PI 3.1415926535897932384626
#define srtv(A) sort((A).begin(), (A).end())
#define rsrtv(v) sort(v.begin(), v.end(), greater <>())
#define srta(a,n) sort(a,a+n)
#define mod 1000000007
#define tolwr(s) transform(s.begin(),s.end(),s.begin(),::toupper);
#define toupr(s) transform(s.begin(),s.end(),s.begin(),::tolower);
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)

using namespace std;
ll pow(ll a,ll b){
    if(a==0)return 0;
    ll x=1;
    while(b>0){
        if(b&1)x=(x*a);
        b=b>>1;
        a=(a*a);
    }
    return x;
}
ll gcdext(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    ll x1,y1,z;
    z=gcdext(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return z;

}
ll findg(ll x){
    ll n=0;
    while(x>0){
        x/=10;
        n++;
    }
    return n;
}
bool cmp(pll a,pll b){
   if(a.ft != b.ft)
    return a.ft<b.ft;
    return a.st<b.st;
}
ll fun(ll n){
    ll x=0;
    while (n % 2 == 0)
    {
        x++;
        n = n/2;
    }
    for (ll i = 3; i*i <= n; i = i + 2)
    {
        
        while (n % i == 0)
        {
            x++;
            n = n/i;
        }
        if(n<i)break;
    }
    if (n > 2)x++;
    return x;
}
int main(){   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);
//ll ww=10000005;
   // ww=100000;
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);   //if input and output is in txt
  
    tc(){
        ll a,b,c,d,i,j,k,l,m,n,p,q,r,x,y,z,ans=0,ind=-1,sum=0;
        string s1;
        
        cin>>a>>b>>n;//cout<<n<<" ";
       
      // x=gcd(a,b);
       //p=a/x;q=b/x;
       //cout<<x<<" "<<p<<" "<<q<<" ";
       if(n==1){
           if((a!=b)&&(a%b==0 || b%a==0))cout<<"YES";
           else cout<<"NO";
       }else{
        p=fun(a);
        q=fun(b);
       // cout<<p<<" "<<q<<" ";
       
        if(p+q>=n)cout<<"YES";
        else{
           cout<<"NO";
        }}
       cout<<"\n";
    }   
    return 0;
} 
### Prompt

Develop a solution in cpp to the problem described below:

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>
#define ll long long int
#define loop(i,k,n) for (ll i = k; i <= n; i++) 
#define rloop(i,k,n) for (ll i = k; i >= n; i--)
#define INF 100000000000
#define umap unordered_map
#define mii map<int,int>
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define pqMin priority_queue<int,vector<int>,greater<int>>
#define pqMax priority_queue<int>
#define pqpii priority_queue<pii>
#define mll map<ll,ll>
#define pll pair<ll,ll>
#define vl vector<ll>
#define vvl vector<vl>
#define vpll vector<pll>
#define ft first 
#define st second                       
#define pb push_back  
#define pob pop_back 
#define mp make_pair 
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define gcd(a,b) __gcd((a),(b))
#define bitcnt(a) __builtin_popcount(a)
#define filla(a, b) memset(a, b, sizeof(a))
#define tc() ll t; cin>>t;while(t--)
#define PI 3.1415926535897932384626
#define srtv(A) sort((A).begin(), (A).end())
#define rsrtv(v) sort(v.begin(), v.end(), greater <>())
#define srta(a,n) sort(a,a+n)
#define mod 1000000007
#define tolwr(s) transform(s.begin(),s.end(),s.begin(),::toupper);
#define toupr(s) transform(s.begin(),s.end(),s.begin(),::tolower);
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)

using namespace std;
ll pow(ll a,ll b){
    if(a==0)return 0;
    ll x=1;
    while(b>0){
        if(b&1)x=(x*a);
        b=b>>1;
        a=(a*a);
    }
    return x;
}
ll gcdext(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    ll x1,y1,z;
    z=gcdext(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return z;

}
ll findg(ll x){
    ll n=0;
    while(x>0){
        x/=10;
        n++;
    }
    return n;
}
bool cmp(pll a,pll b){
   if(a.ft != b.ft)
    return a.ft<b.ft;
    return a.st<b.st;
}
ll fun(ll n){
    ll x=0;
    while (n % 2 == 0)
    {
        x++;
        n = n/2;
    }
    for (ll i = 3; i*i <= n; i = i + 2)
    {
        
        while (n % i == 0)
        {
            x++;
            n = n/i;
        }
        if(n<i)break;
    }
    if (n > 2)x++;
    return x;
}
int main(){   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);
//ll ww=10000005;
   // ww=100000;
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);   //if input and output is in txt
  
    tc(){
        ll a,b,c,d,i,j,k,l,m,n,p,q,r,x,y,z,ans=0,ind=-1,sum=0;
        string s1;
        
        cin>>a>>b>>n;//cout<<n<<" ";
       
      // x=gcd(a,b);
       //p=a/x;q=b/x;
       //cout<<x<<" "<<p<<" "<<q<<" ";
       if(n==1){
           if((a!=b)&&(a%b==0 || b%a==0))cout<<"YES";
           else cout<<"NO";
       }else{
        p=fun(a);
        q=fun(b);
       // cout<<p<<" "<<q<<" ";
       
        if(p+q>=n)cout<<"YES";
        else{
           cout<<"NO";
        }}
       cout<<"\n";
    }   
    return 0;
} 
```