#include <bits/stdc++.h> 

using namespace std; 
#define ll long long
 
#define pii pair<int,int>
#define pll pair<ll,ll>
 
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define vpi vector<pii>
#define vpl vector<pll>
#define pb push_back
#define all(v) v.begin(),v.end()
#define fast_io ios_base::sync_with_stdio(0),cin.tie(0);
 
 
template <class T>
void print(vector<T> a) {
	cout<<a[0];
    for(ll i = 1; i < a.size(); ++i) {
        cout <<' '<<a[i];
    }
    cout<<"\n";
}
 
int sum_vector(vi v){
	return accumulate(all(v),0);
}
 
void sort_vector(vi&v){
	sort(all(v));
}
 
void sort_comp(vi &v, bool func(int,int)){
	sort(all(v),func);
}
 

bool comp(array<__int128_t,5> a, array<__int128_t,5> b){
	return a[2]*a[1]*b[3]*b[0]<b[2]*b[1]*a[3]*a[0];
}
 
ll gcd(ll a, ll b){
	a=abs(a);
	b=abs(b);
	while(a){
		ll temp =a;
		a=b%a;
		b=temp;
	}
	return abs(b);
}
 
ll lcm(ll a, ll b){
	return (a*b)/gcd(a,b);
}
 
string binary(ll num){
	string ans="";
	do{
		ans=to_string(num%2)+ans;
		num/=2;
	}while(num);
	return ans;
}
 
const int mxn = 1e5+7;
const int d = 18;
const int mill = 1e6+3;
const ll mod = 1e9+7; 
 
ll pwr(ll num, ll p){
	ll res=1;
	while(p>0){
		if(p&1) res=(res*num)%mod;
		num=(num*num)%mod;
		p/=2;
	}
	return res;
}
 
ll inverse(ll num){
	return pwr(num,mod-2);
}


const int N=4e4+3;
vb isprime(N,1);
vll primes={};

int facs (ll x){
	int p=0;
	int count=0;
	while(x!=1 && p!=primes.size()){
if(primes[p]*primes[p]>x) break;
		while(x%primes[p]==0){
			x/=primes[p];
			count++;
		}
		p++;
	}
	if(x!=1){
		return count+1;
	}
	return count;
}

void solve(){
	ll a,b,k;
	cin>>a>>b>>k;
	if(a*b==1 || k>65){
		cout<<"NO\n";
		return;
	}
	if(k==1){
		if(a==b){
			cout<<"NO\n";
		}
		else if(a%b==0 || b%a==0){
			cout<<"YES\n";
		}
		else{
			cout<<"NO\n";
		}
		return;
	}
	if(facs(a)+facs(b)>=k){
		cout<<"YES\n";
	}
	else{
		cout<<"NO\n";
	}
}
 
 
int main()
{
	fast_io
	int t=1;
	cin>>t;
	bool found;
	for (int i=2; i<N; i++) {
		if(isprime[i]==0) continue;
		for(int j=2*i;j<N;j+=i){
			isprime[j]=0;
		}
	}
	for(int i=2;i<N;i++){
		if(isprime[i]) primes.pb(i);
	}
	
	for(int ii=1;ii<=t;ii++){
		solve();
	}
	
	
	return 0;
}

### Prompt

In CPP, your task is to solve 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
 
#define pii pair<int,int>
#define pll pair<ll,ll>
 
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define vpi vector<pii>
#define vpl vector<pll>
#define pb push_back
#define all(v) v.begin(),v.end()
#define fast_io ios_base::sync_with_stdio(0),cin.tie(0);
 
 
template <class T>
void print(vector<T> a) {
	cout<<a[0];
    for(ll i = 1; i < a.size(); ++i) {
        cout <<' '<<a[i];
    }
    cout<<"\n";
}
 
int sum_vector(vi v){
	return accumulate(all(v),0);
}
 
void sort_vector(vi&v){
	sort(all(v));
}
 
void sort_comp(vi &v, bool func(int,int)){
	sort(all(v),func);
}
 

bool comp(array<__int128_t,5> a, array<__int128_t,5> b){
	return a[2]*a[1]*b[3]*b[0]<b[2]*b[1]*a[3]*a[0];
}
 
ll gcd(ll a, ll b){
	a=abs(a);
	b=abs(b);
	while(a){
		ll temp =a;
		a=b%a;
		b=temp;
	}
	return abs(b);
}
 
ll lcm(ll a, ll b){
	return (a*b)/gcd(a,b);
}
 
string binary(ll num){
	string ans="";
	do{
		ans=to_string(num%2)+ans;
		num/=2;
	}while(num);
	return ans;
}
 
const int mxn = 1e5+7;
const int d = 18;
const int mill = 1e6+3;
const ll mod = 1e9+7; 
 
ll pwr(ll num, ll p){
	ll res=1;
	while(p>0){
		if(p&1) res=(res*num)%mod;
		num=(num*num)%mod;
		p/=2;
	}
	return res;
}
 
ll inverse(ll num){
	return pwr(num,mod-2);
}


const int N=4e4+3;
vb isprime(N,1);
vll primes={};

int facs (ll x){
	int p=0;
	int count=0;
	while(x!=1 && p!=primes.size()){
if(primes[p]*primes[p]>x) break;
		while(x%primes[p]==0){
			x/=primes[p];
			count++;
		}
		p++;
	}
	if(x!=1){
		return count+1;
	}
	return count;
}

void solve(){
	ll a,b,k;
	cin>>a>>b>>k;
	if(a*b==1 || k>65){
		cout<<"NO\n";
		return;
	}
	if(k==1){
		if(a==b){
			cout<<"NO\n";
		}
		else if(a%b==0 || b%a==0){
			cout<<"YES\n";
		}
		else{
			cout<<"NO\n";
		}
		return;
	}
	if(facs(a)+facs(b)>=k){
		cout<<"YES\n";
	}
	else{
		cout<<"NO\n";
	}
}
 
 
int main()
{
	fast_io
	int t=1;
	cin>>t;
	bool found;
	for (int i=2; i<N; i++) {
		if(isprime[i]==0) continue;
		for(int j=2*i;j<N;j+=i){
			isprime[j]=0;
		}
	}
	for(int i=2;i<N;i++){
		if(isprime[i]) primes.pb(i);
	}
	
	for(int ii=1;ii<=t;ii++){
		solve();
	}
	
	
	return 0;
}

```