#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define pdd pair<double,double>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define mp make_pair
#define LL long long
#define ULL unsigned long long
#define sqr(x) ((x)*(x))
#define pi acosl(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
using namespace std;
#define last Last
#define MXN 200005
const int mod=1e9+7;
void solve(){
    int a,b,k;
    scanf("%d %d %d",&a,&b,&k);
    if(a>b)swap(a,b);
    if(k==1){
        if(b%a==0){
            if(a==b)printf("NO\n");
            else printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    else{
        int Max=0;
        for(int i = 2;i*i<=a;i++){
            while(a%i==0){
                Max++;
                a/=i;
            }
        }
        if(a!=1)Max++;
        for(int i = 2;i*i<=b;i++){
            while(b%i==0){
                Max++;
                b/=i;
            }
        }
        if(b!=1)Max++;
        if(k<=Max){
            printf("YEs\n");
        }
        else{
            printf("NO\n");
        }
    }
}
int main(){
    int t=1;
    scanf("%d",&t);
    while(t--)
        solve();
}
/*
2 3 5 6 1 4
*/
### 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
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define pdd pair<double,double>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define mp make_pair
#define LL long long
#define ULL unsigned long long
#define sqr(x) ((x)*(x))
#define pi acosl(-1)
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
using namespace std;
#define last Last
#define MXN 200005
const int mod=1e9+7;
void solve(){
    int a,b,k;
    scanf("%d %d %d",&a,&b,&k);
    if(a>b)swap(a,b);
    if(k==1){
        if(b%a==0){
            if(a==b)printf("NO\n");
            else printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    else{
        int Max=0;
        for(int i = 2;i*i<=a;i++){
            while(a%i==0){
                Max++;
                a/=i;
            }
        }
        if(a!=1)Max++;
        for(int i = 2;i*i<=b;i++){
            while(b%i==0){
                Max++;
                b/=i;
            }
        }
        if(b!=1)Max++;
        if(k<=Max){
            printf("YEs\n");
        }
        else{
            printf("NO\n");
        }
    }
}
int main(){
    int t=1;
    scanf("%d",&t);
    while(t--)
        solve();
}
/*
2 3 5 6 1 4
*/
```