#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string.h>
#include <cmath>
#include <iomanip> 
#include <ios> 
#include <sstream>
#include <stack>
#include <numeric>
#include <limits.h>
#define ll long long
const int32_t M=1e9+7;

using namespace std;

const ll MAX_SIZE = 100005;
vector<ll >isprime(MAX_SIZE , true);
vector<ll >prime;
vector<ll >SPF(MAX_SIZE);
void manipulated_seive(ll N=(MAX_SIZE-5))
{
    isprime[0] = isprime[1] = false ;
    for (ll i=2; i<N ; i++)
    {
        if (isprime[i])
        {
            prime.push_back(i);
            SPF[i] = i;
        }
        // Remove all multiples of  i*prime[j] which are
        // not prime by making isPrime[i*prime[j]] = false
        // and put smallest prime factor of i*Prime[j] as prime[j]
        // [ for exp :let  i = 5 , j = 0 , prime[j] = 2 [ i*prime[j] = 10 ]
        // so smallest prime factor of '10' is '2' that is prime[j] ]
        // this loop run only one time for number which are not prime
        for (ll j=0;j<(ll)prime.size() && i*prime[j] < N && prime[j] <= SPF[i];j++)
        {
            isprime[i*prime[j]]=false;
            SPF[i*prime[j]] = prime[j] ;
        }
    }
}

ll f(ll x)
{
    ll cnt=0;
    for(ll i=0;i<prime.size();i++)
    {
        if(prime[i]>x)
            break;
        while(x%prime[i] == 0)
        {
            x/=prime[i];
            cnt++;
        }
    }
    if(x>1)
        cnt++;
    return cnt;
}

void solve()
{
    ll a,b,k;
    scanf("%lld %lld %lld",&a,&b,&k);
    if(b<a) swap(a,b);
    if(k==1)
    {
        if(b%a==0 && a!=b)
            printf("YES\n");
        else
            printf("NO\n");
    }
    else if(k>=70)
    {
        printf("NO\n");
    }
    else if(f(a)+f(b) >= k)
        printf("YES\n");
    else
        printf("NO\n");

}

// Do not quit
// Keep trying, you're close
// No looking at standings
// Atleat C

int main(void)
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ll t=1;
	scanf("%lld",&t);
    manipulated_seive();
	for(ll i=1;i<=t;i++)
	{
		// printf("Case #%lld: ",i);
		solve();
	}
}




### Prompt

Your task is to create 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 <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string.h>
#include <cmath>
#include <iomanip> 
#include <ios> 
#include <sstream>
#include <stack>
#include <numeric>
#include <limits.h>
#define ll long long
const int32_t M=1e9+7;

using namespace std;

const ll MAX_SIZE = 100005;
vector<ll >isprime(MAX_SIZE , true);
vector<ll >prime;
vector<ll >SPF(MAX_SIZE);
void manipulated_seive(ll N=(MAX_SIZE-5))
{
    isprime[0] = isprime[1] = false ;
    for (ll i=2; i<N ; i++)
    {
        if (isprime[i])
        {
            prime.push_back(i);
            SPF[i] = i;
        }
        // Remove all multiples of  i*prime[j] which are
        // not prime by making isPrime[i*prime[j]] = false
        // and put smallest prime factor of i*Prime[j] as prime[j]
        // [ for exp :let  i = 5 , j = 0 , prime[j] = 2 [ i*prime[j] = 10 ]
        // so smallest prime factor of '10' is '2' that is prime[j] ]
        // this loop run only one time for number which are not prime
        for (ll j=0;j<(ll)prime.size() && i*prime[j] < N && prime[j] <= SPF[i];j++)
        {
            isprime[i*prime[j]]=false;
            SPF[i*prime[j]] = prime[j] ;
        }
    }
}

ll f(ll x)
{
    ll cnt=0;
    for(ll i=0;i<prime.size();i++)
    {
        if(prime[i]>x)
            break;
        while(x%prime[i] == 0)
        {
            x/=prime[i];
            cnt++;
        }
    }
    if(x>1)
        cnt++;
    return cnt;
}

void solve()
{
    ll a,b,k;
    scanf("%lld %lld %lld",&a,&b,&k);
    if(b<a) swap(a,b);
    if(k==1)
    {
        if(b%a==0 && a!=b)
            printf("YES\n");
        else
            printf("NO\n");
    }
    else if(k>=70)
    {
        printf("NO\n");
    }
    else if(f(a)+f(b) >= k)
        printf("YES\n");
    else
        printf("NO\n");

}

// Do not quit
// Keep trying, you're close
// No looking at standings
// Atleat C

int main(void)
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ll t=1;
	scanf("%lld",&t);
    manipulated_seive();
	for(ll i=1;i<=t;i++)
	{
		// printf("Case #%lld: ",i);
		solve();
	}
}




```