#include<bits/stdc++.h>
using namespace std;
#define pfi(a) printf("%d",a);
#define pfl(a) printf("%lld",a);
#define pfin(a) printf("%d\n",a);
#define pfln(a) printf("%lld\n",a);
#define pfis(a) printf("%d ",a);
#define pfls(a) printf("%lld ",a);
#define sfi(a) scanf("%d",&a);
#define sfl(a) scanf("%lld",&a);
#define f(i,a,b) for(int i=a;i<b;i++)
#define pb(a) push_back(a)
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define bp(i) __builtin_popcount(i)

ll mod=1e9+7;
vector<int>v;
void prime()
{
 int a[100002];
  for(int i=0;i<=100001;i++)
  {
	a[i]=i;
  }
//   cout<<1<<endl;
  for(int i=2;i*i<=100001;i++)
  {
	    if(a[i]==i)
        {
    	  for(int j=i*i;j<=100001;j+=i)
    	   {
    		    a[j]=i;
    	   }
	    }
  }
  for(int i=2;i<=100001;i++)
  {
    if(a[i]==i)
	    v.pb(i);
  }
}

int main() {
    fast;
	int t;
	cin>>t;
	prime();
// 	cout<<t<<endl;
	while(t--)
	{
	    int a,b,k,cnt=0;
	    cin>>a>>b>>k;
	    if(a==1 && b==1)
	    {
	        cout<<"NO"<<endl;
	        continue;
	    }
	    if(k==1)
	    {
	       
	        if(a!=b && (a%b==0 || b%a==0))
	        {
	            cout<<"YES"<<endl;
	        }
	        else
	        {
	            cout<<"NO"<<endl;
	        }
	        continue;
	    }
	    for(int i=0;i<v.size() && a>1;i++)
	    {
	       // cout<<a<<' '<<v[i]<<endl;
	        while(a%v[i]==0)
	        {
	            cnt++;
	            a/=v[i];
	        }
	       // cout<<cnt<<endl;
	    }
	    if(a>1)
	        cnt++;
	    for(int i=0;i<v.size() && b>1;i++)
	    {
	        while(b%v[i]==0)
	        {
	            cnt++;
	            b/=v[i];
	        }
	    }
	    if(b>1)
	        cnt++;
	    
	    if(cnt>=k)
	        cout<<"YES"<<endl;
	    else
	        cout<<"NO"<<endl;
	    
	}
	return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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 pfi(a) printf("%d",a);
#define pfl(a) printf("%lld",a);
#define pfin(a) printf("%d\n",a);
#define pfln(a) printf("%lld\n",a);
#define pfis(a) printf("%d ",a);
#define pfls(a) printf("%lld ",a);
#define sfi(a) scanf("%d",&a);
#define sfl(a) scanf("%lld",&a);
#define f(i,a,b) for(int i=a;i<b;i++)
#define pb(a) push_back(a)
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define bp(i) __builtin_popcount(i)

ll mod=1e9+7;
vector<int>v;
void prime()
{
 int a[100002];
  for(int i=0;i<=100001;i++)
  {
	a[i]=i;
  }
//   cout<<1<<endl;
  for(int i=2;i*i<=100001;i++)
  {
	    if(a[i]==i)
        {
    	  for(int j=i*i;j<=100001;j+=i)
    	   {
    		    a[j]=i;
    	   }
	    }
  }
  for(int i=2;i<=100001;i++)
  {
    if(a[i]==i)
	    v.pb(i);
  }
}

int main() {
    fast;
	int t;
	cin>>t;
	prime();
// 	cout<<t<<endl;
	while(t--)
	{
	    int a,b,k,cnt=0;
	    cin>>a>>b>>k;
	    if(a==1 && b==1)
	    {
	        cout<<"NO"<<endl;
	        continue;
	    }
	    if(k==1)
	    {
	       
	        if(a!=b && (a%b==0 || b%a==0))
	        {
	            cout<<"YES"<<endl;
	        }
	        else
	        {
	            cout<<"NO"<<endl;
	        }
	        continue;
	    }
	    for(int i=0;i<v.size() && a>1;i++)
	    {
	       // cout<<a<<' '<<v[i]<<endl;
	        while(a%v[i]==0)
	        {
	            cnt++;
	            a/=v[i];
	        }
	       // cout<<cnt<<endl;
	    }
	    if(a>1)
	        cnt++;
	    for(int i=0;i<v.size() && b>1;i++)
	    {
	        while(b%v[i]==0)
	        {
	            cnt++;
	            b/=v[i];
	        }
	    }
	    if(b>1)
	        cnt++;
	    
	    if(cnt>=k)
	        cout<<"YES"<<endl;
	    else
	        cout<<"NO"<<endl;
	    
	}
	return 0;
}

```