#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define ld long double
#define pb push_back
#define pp pop_back
#define shubhAm 0

#define ML 1e9

#define foru(i,a,b) for(ll i = (ll)(a) ; i <(ll)(b) ; i++)
#define ford(i,a,b) for(ll i = (ll)(a) ; i >= (ll)(b) ; i--)

bool isPSquare(ld a){if (a>=0) {ll h = sqrt(a);return (h*h == a);}else return false;}
bool isPal(string s) {ll n=s.length(); for (ll i = 0; i < n/2; i++) {if(s[i]!=s[n-i-1]) return false;} return true;}
ll fact(ll a) {if (a<=1) {return 1;} return a*fact(a-1);}
ll ncr(ll n,ll r) {ll res=1; for (int i=0; i<r; i++) {res*= (n-i);res/= (i+1);} return res;}
bool allSame(string s){ll n = s.length(); for (ll i = 1; i < n; i++) if (s[i] !=s[0]) return false; return true;}
bool isPrime(ll a) {if (a<=1) return false; for (int i = 2; i <a; i++) if (a % i == 0) return false; return true;}
ll gcd(ll a,ll b) {if (b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a,ll b) {return (a / gcd(a, b)) * b;}

vector<ll> pm;
void construct()
{
    for(ll i=0;i*i<=ML;i++)
    {
        if(isPrime(i))
            pm.pb(i);
    }
}
ll cpf(ll a)
{
    ll count=0;
    for (auto i:pm) 
    {
        if (a%i==0)
        {
            while (a%i==0)
            {
                ++count;
                a/=i;
            }
        }
    }
    if(a>1)
        ++count;
    return count;
}
void hue_hue_hue()
{
    ll a,b,k;
    cin>>a>>b>>k;
    if(k==1)
    {
        if(a==b)
        {
            cout<<"NO\n";
            return;
        }
        if(a%b==0||b%a==0)
            cout<<"YES\n";
        else
        {
            cout<<"NO\n";
        }
        return;
    }
    ll ch=cpf(a)+cpf(b);
    //cout<<cpf(a)<<" : "<<cpf(b)<<endl;
    if(k<=ch)
        cout<<"YES\n";
    else
        cout<<"NO\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
        // #ifndef ONLINE_JUDGE
        // freopen("input.txt","r",stdin);
        // freopen("output.txt","w",stdout);
        // #endif
    // cout<<fixed<<setprecision(9);
    construct();
    ll testCase=1;
    cin>>testCase;
    while (testCase-->shubhAm) hue_hue_hue();
    return shubhAm;
}
### Prompt

Your challenge is to write 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 ll long long int
#define ld long double
#define pb push_back
#define pp pop_back
#define shubhAm 0

#define ML 1e9

#define foru(i,a,b) for(ll i = (ll)(a) ; i <(ll)(b) ; i++)
#define ford(i,a,b) for(ll i = (ll)(a) ; i >= (ll)(b) ; i--)

bool isPSquare(ld a){if (a>=0) {ll h = sqrt(a);return (h*h == a);}else return false;}
bool isPal(string s) {ll n=s.length(); for (ll i = 0; i < n/2; i++) {if(s[i]!=s[n-i-1]) return false;} return true;}
ll fact(ll a) {if (a<=1) {return 1;} return a*fact(a-1);}
ll ncr(ll n,ll r) {ll res=1; for (int i=0; i<r; i++) {res*= (n-i);res/= (i+1);} return res;}
bool allSame(string s){ll n = s.length(); for (ll i = 1; i < n; i++) if (s[i] !=s[0]) return false; return true;}
bool isPrime(ll a) {if (a<=1) return false; for (int i = 2; i <a; i++) if (a % i == 0) return false; return true;}
ll gcd(ll a,ll b) {if (b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a,ll b) {return (a / gcd(a, b)) * b;}

vector<ll> pm;
void construct()
{
    for(ll i=0;i*i<=ML;i++)
    {
        if(isPrime(i))
            pm.pb(i);
    }
}
ll cpf(ll a)
{
    ll count=0;
    for (auto i:pm) 
    {
        if (a%i==0)
        {
            while (a%i==0)
            {
                ++count;
                a/=i;
            }
        }
    }
    if(a>1)
        ++count;
    return count;
}
void hue_hue_hue()
{
    ll a,b,k;
    cin>>a>>b>>k;
    if(k==1)
    {
        if(a==b)
        {
            cout<<"NO\n";
            return;
        }
        if(a%b==0||b%a==0)
            cout<<"YES\n";
        else
        {
            cout<<"NO\n";
        }
        return;
    }
    ll ch=cpf(a)+cpf(b);
    //cout<<cpf(a)<<" : "<<cpf(b)<<endl;
    if(k<=ch)
        cout<<"YES\n";
    else
        cout<<"NO\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
        // #ifndef ONLINE_JUDGE
        // freopen("input.txt","r",stdin);
        // freopen("output.txt","w",stdout);
        // #endif
    // cout<<fixed<<setprecision(9);
    construct();
    ll testCase=1;
    cin>>testCase;
    while (testCase-->shubhAm) hue_hue_hue();
    return shubhAm;
}
```