//codeforces
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define For(i,a,b) for(i=a;i<b;i++)
#define eb emplace_back
//#define get getchar_unlocked 
#define sortV(a) sort(a.begin(),a.end()) 
#define sortA(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define INF 0x3f3f3f3f 
#define line "\n"
typedef pair<long long int,long long int>Pair;
static long long int mod=(long long)(1e9)+7;
ll prime(int n)
{
  ll ans=0;
    while(n % 2 == 0)
    {
        ans++;
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        while (n % i == 0)
        {
            ans++;
            n = n/i;
        }
    }
    if (n > 2) ans++;
    return ans;
}  
void solve(){
ll t,n,i,k,j,q,d;
string str;
char ch[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; 
cin>>i>>j>>k;
if(k==1){
  ll mini=min(i,j);
  ll maxi=max(i,j);
  if(maxi%mini==0&&mini!=maxi) cout<<"YES\n";
  else cout<<"NO\n";
  return;
}
if(i==1&&j==1){
  cout<<"NO"<<line;
  return ;
}

ll val=0;
ll a1=prime(i);
ll a2=prime(j);
val+=a1;
val+=a2;
if(val>=k) cout<<"YES\n";
else cout<<"NO\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t;
cin>>t;
while(t--)
{
  solve();
}
return 0;
}
### Prompt

Develop a solution in cpp 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
//codeforces
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define For(i,a,b) for(i=a;i<b;i++)
#define eb emplace_back
//#define get getchar_unlocked 
#define sortV(a) sort(a.begin(),a.end()) 
#define sortA(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define INF 0x3f3f3f3f 
#define line "\n"
typedef pair<long long int,long long int>Pair;
static long long int mod=(long long)(1e9)+7;
ll prime(int n)
{
  ll ans=0;
    while(n % 2 == 0)
    {
        ans++;
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        while (n % i == 0)
        {
            ans++;
            n = n/i;
        }
    }
    if (n > 2) ans++;
    return ans;
}  
void solve(){
ll t,n,i,k,j,q,d;
string str;
char ch[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; 
cin>>i>>j>>k;
if(k==1){
  ll mini=min(i,j);
  ll maxi=max(i,j);
  if(maxi%mini==0&&mini!=maxi) cout<<"YES\n";
  else cout<<"NO\n";
  return;
}
if(i==1&&j==1){
  cout<<"NO"<<line;
  return ;
}

ll val=0;
ll a1=prime(i);
ll a2=prime(j);
val+=a1;
val+=a2;
if(val>=k) cout<<"YES\n";
else cout<<"NO\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t;
cin>>t;
while(t--)
{
  solve();
}
return 0;
}
```