#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define mp make_pair
#define vc vector<ll>
#define append pb
#define fo(n) for(int i=0;i<n;i++)
#define foj(m,n) for(int j=m;j<n;j++)
#define N ((ll)8e5+5)
#define print(a) cout<<a<<endl;
using namespace std;
vc l;
void ss(int n)
{

    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p])
            l.pb(p);
}
signed main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin); 
	freopen("outpt.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll t;
	t=1;
	cin>>t;
	ss(31625);
	//print(l.size())
	while(t--)
	{
		ll a,b,k;
	cin>>a>>b>>k;
	int na=a,nb=b;
	ll i=2,c=0,d=0;
	for(auto i: l){
		if(i>max(a,b)) break;
		if(a%i==0) while(a%i==0) a/=i,c++;
		if(b%i==0) while(b%i==0) b/=i,d++;
		if(c+d>=k) break;
	}
	if(a>=2) c++;
	if(b>=2) d++;
	
	if(k==1){
		if((na%nb==0 or nb%na==0) and na!=nb) print("YES")
			else print("NO")
	}
	else{
		if(c+d>=k) print("YES")
			else print("NO")
	}
	}
	return 0;
}
### Prompt

Create a solution in cpp for 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>
#define ll long long
#define int ll
#define pb push_back
#define mp make_pair
#define vc vector<ll>
#define append pb
#define fo(n) for(int i=0;i<n;i++)
#define foj(m,n) for(int j=m;j<n;j++)
#define N ((ll)8e5+5)
#define print(a) cout<<a<<endl;
using namespace std;
vc l;
void ss(int n)
{

    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++)
        if (prime[p])
            l.pb(p);
}
signed main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin); 
	freopen("outpt.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll t;
	t=1;
	cin>>t;
	ss(31625);
	//print(l.size())
	while(t--)
	{
		ll a,b,k;
	cin>>a>>b>>k;
	int na=a,nb=b;
	ll i=2,c=0,d=0;
	for(auto i: l){
		if(i>max(a,b)) break;
		if(a%i==0) while(a%i==0) a/=i,c++;
		if(b%i==0) while(b%i==0) b/=i,d++;
		if(c+d>=k) break;
	}
	if(a>=2) c++;
	if(b>=2) d++;
	
	if(k==1){
		if((na%nb==0 or nb%na==0) and na!=nb) print("YES")
			else print("NO")
	}
	else{
		if(c+d>=k) print("YES")
			else print("NO")
	}
	}
	return 0;
}
```