#include "bits/stdc++.h"
#define int long long
#define fi first
#define se second
#define ln cout<<"\n"
using namespace std;
const int N = 1e5+2;
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
#define print1(x) for(auto v:x){cout<<v<<' ';}
template<typename T>
void print(T t){cout<<(t);cout<<'\n';}
template<typename T, typename... Args>
void print(T t, Args... args){cout << (t) <<' ';print(args...);}
vector<int>primes;
bool isPrime[40000];
int f(int n){
    int a=0,m=n;
    for(int v:primes){
        while(n%v==0){
            a++;
            n/=v;
        }
    }
    if(n>1)a++;
    return a;
}
void calc(){
    int N = 40000;
    for(int i=2;i<N;i++){
        if(isPrime[i])primes.push_back(i);
        for(int j =2*i;j<N;j+=i){
            isPrime[j] = false;
        }
    }
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    memset(isPrime,1,sizeof(isPrime));
    calc();
    int test;cin>>test;
    while(test--){
        int a,b,k;cin>>a>>b>>k;
        if(k==1){
            if(a!=b and(b%a == 0 or a%b==0))print("YES");
            else print("NO");
            continue;
        }
        int A=f(a);
        int B = f(b);
        if(A+B>=k)print("YES");
        else print("NO");
    }
    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"
#define int long long
#define fi first
#define se second
#define ln cout<<"\n"
using namespace std;
const int N = 1e5+2;
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
#define print1(x) for(auto v:x){cout<<v<<' ';}
template<typename T>
void print(T t){cout<<(t);cout<<'\n';}
template<typename T, typename... Args>
void print(T t, Args... args){cout << (t) <<' ';print(args...);}
vector<int>primes;
bool isPrime[40000];
int f(int n){
    int a=0,m=n;
    for(int v:primes){
        while(n%v==0){
            a++;
            n/=v;
        }
    }
    if(n>1)a++;
    return a;
}
void calc(){
    int N = 40000;
    for(int i=2;i<N;i++){
        if(isPrime[i])primes.push_back(i);
        for(int j =2*i;j<N;j+=i){
            isPrime[j] = false;
        }
    }
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    memset(isPrime,1,sizeof(isPrime));
    calc();
    int test;cin>>test;
    while(test--){
        int a,b,k;cin>>a>>b>>k;
        if(k==1){
            if(a!=b and(b%a == 0 or a%b==0))print("YES");
            else print("NO");
            continue;
        }
        int A=f(a);
        int B = f(b);
        if(A+B>=k)print("YES");
        else print("NO");
    }
    return 0;
}

```