#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ppll pair<ll,pair<ll,ll>>
#define pll pair<ll,ll>
#define rep(i,x,y) for(ll i=x;i<=y;i++)
#define inf 1e16
#define imin INT_MIN
#define imax INT_MAX
#define pb push_back
#define pf push_front
#define vll vector<ll> 
#define vvll vector<vector<ll>>
#define vvb vector<vector<bool>>
#define vb vector<bool>
int mod =1e9+7;
bool comp(pair<int,int> a,pair<int,int> b)
{
    if(a.second == b.second) return a.first<b.first;
    return a.second<b.second;
}

void display(vll a)
{
    for(auto& val: a) cout<<val<<' ';
}

ll power(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if (b & 1) ans = (ans * a)%mod;
        a  = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

const int N = 40000;
bool prime[N + 1];
vll primes;
void setup()
{
    for(ll i = 2;i <= N;i++) {
        if(prime[i]) {
            primes.pb(i);
            for(ll j = i*i;j <= N;j+= i)
                prime[j] = false;
        }   
    }
}

ll cntPF(ll x)
{
    ll cnt = 0;
    for(auto i: primes)
    {
        while(x % i == 0)
            x /= i, cnt++;
    }
    if(x > 1) cnt++;
    return cnt;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    rep(i,1,N) prime[i] = true;
    setup();
    ll t;
    cin>>t;
    while(t--)
    {   
        ll a, b, k;
        cin>>a>>b>>k;
        if(k == 1)
        {
            if((a%b == 0 || b % a == 0) && (a != b)) cout<<"YES\n";
            else cout<<"NO\n";
            continue;
        }
        ll total = cntPF(a) + cntPF(b);
        cout<< ((total >= k) ? "YES\n" : "NO\n");
    }
    return 0;
}

### 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;
typedef long long ll;
#define ppll pair<ll,pair<ll,ll>>
#define pll pair<ll,ll>
#define rep(i,x,y) for(ll i=x;i<=y;i++)
#define inf 1e16
#define imin INT_MIN
#define imax INT_MAX
#define pb push_back
#define pf push_front
#define vll vector<ll> 
#define vvll vector<vector<ll>>
#define vvb vector<vector<bool>>
#define vb vector<bool>
int mod =1e9+7;
bool comp(pair<int,int> a,pair<int,int> b)
{
    if(a.second == b.second) return a.first<b.first;
    return a.second<b.second;
}

void display(vll a)
{
    for(auto& val: a) cout<<val<<' ';
}

ll power(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if (b & 1) ans = (ans * a)%mod;
        a  = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

const int N = 40000;
bool prime[N + 1];
vll primes;
void setup()
{
    for(ll i = 2;i <= N;i++) {
        if(prime[i]) {
            primes.pb(i);
            for(ll j = i*i;j <= N;j+= i)
                prime[j] = false;
        }   
    }
}

ll cntPF(ll x)
{
    ll cnt = 0;
    for(auto i: primes)
    {
        while(x % i == 0)
            x /= i, cnt++;
    }
    if(x > 1) cnt++;
    return cnt;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    rep(i,1,N) prime[i] = true;
    setup();
    ll t;
    cin>>t;
    while(t--)
    {   
        ll a, b, k;
        cin>>a>>b>>k;
        if(k == 1)
        {
            if((a%b == 0 || b % a == 0) && (a != b)) cout<<"YES\n";
            else cout<<"NO\n";
            continue;
        }
        ll total = cntPF(a) + cntPF(b);
        cout<< ((total >= k) ? "YES\n" : "NO\n");
    }
    return 0;
}

```