#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<iomanip>
#include<math.h>
#include<math.h>
#include<queue>
using namespace std;
#define pb push_back
#define ll long long int
# define pll pair<ll,ll>
#define sec second
#define ft first
#define mp make_pair
# define fio ios_base::sync_with_stdio(false); cin.tie(NULL)
ll a,b,k;
vector<ll>p ;
ll get(ll x)
{
    ll ans = 0 ;
    for(int j = 0 ; j < p.size() and p[j]*p[j] <= 1e9 ; j++)
    {
        ll i = p[j];
        while(x%i == 0)
        {
            ans++;
            x/=i;
        }
        if(ans >= 60) break ;
        if(x == 1) break;
    }
    ans+=(x!=1);
    return ans;
}
ll gcd(ll x  , ll y)
{
    if( x == 0) return y ;
    return gcd(y%x,x);
}
void solve()
{
    cin >> a >> b >> k ;
    if(k >= 60 )  {cout << "NO\n" ; return ; }
    else if(k == 1)
    {
        if(a != b and gcd(a,b) == min(a,b)) cout << "YES\n";
        else cout << "NO\n";
    }
    else if( (1ll<<k) > a*b)
    {
        cout << "NO\n";
        return  ;
    }
    else
    {
    ll cnta = get(a) , cntb = get(b);
        if(cnta+cntb >= k) cout << "YES\n";
        else cout <<"NO\n";
    }
    
}
int main()
{
    fio;
    int t =  1 ;
    cin >> t ;
    bool n[200009] ;
    n[1] = true;
    n[2] = false;
    for(int i = 2 ; i*i <= 2*1e5 ; i++)
    {
         if(!n[i])
         {
             for(int j = i*i ; j <= 2*1e5 ; j+=i) n[j] = true;
         }
    }
    for(int i = 2 ; i <= 2*1e5 ; i++) if(!n[i]) p.pb(i);
  //  for(int x : p) cout << x <<" " ; cout <<"\n";
    //cout << v.back()<<"\n";
    for(int cs = 1 ; cs <= t ; cs ++ )
    {
       // cout <<"Case #"<<cs<<": ";
        solve();
    }
}


### 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<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<iomanip>
#include<math.h>
#include<math.h>
#include<queue>
using namespace std;
#define pb push_back
#define ll long long int
# define pll pair<ll,ll>
#define sec second
#define ft first
#define mp make_pair
# define fio ios_base::sync_with_stdio(false); cin.tie(NULL)
ll a,b,k;
vector<ll>p ;
ll get(ll x)
{
    ll ans = 0 ;
    for(int j = 0 ; j < p.size() and p[j]*p[j] <= 1e9 ; j++)
    {
        ll i = p[j];
        while(x%i == 0)
        {
            ans++;
            x/=i;
        }
        if(ans >= 60) break ;
        if(x == 1) break;
    }
    ans+=(x!=1);
    return ans;
}
ll gcd(ll x  , ll y)
{
    if( x == 0) return y ;
    return gcd(y%x,x);
}
void solve()
{
    cin >> a >> b >> k ;
    if(k >= 60 )  {cout << "NO\n" ; return ; }
    else if(k == 1)
    {
        if(a != b and gcd(a,b) == min(a,b)) cout << "YES\n";
        else cout << "NO\n";
    }
    else if( (1ll<<k) > a*b)
    {
        cout << "NO\n";
        return  ;
    }
    else
    {
    ll cnta = get(a) , cntb = get(b);
        if(cnta+cntb >= k) cout << "YES\n";
        else cout <<"NO\n";
    }
    
}
int main()
{
    fio;
    int t =  1 ;
    cin >> t ;
    bool n[200009] ;
    n[1] = true;
    n[2] = false;
    for(int i = 2 ; i*i <= 2*1e5 ; i++)
    {
         if(!n[i])
         {
             for(int j = i*i ; j <= 2*1e5 ; j+=i) n[j] = true;
         }
    }
    for(int i = 2 ; i <= 2*1e5 ; i++) if(!n[i]) p.pb(i);
  //  for(int x : p) cout << x <<" " ; cout <<"\n";
    //cout << v.back()<<"\n";
    for(int cs = 1 ; cs <= t ; cs ++ )
    {
       // cout <<"Case #"<<cs<<": ";
        solve();
    }
}


```