#include<bits/stdc++.h>

using namespace std ;
//it ain't much but it's honest work
const int MAX_N=2e5+10 ;
int a[MAX_N] ;

// just dont look

vector<int>A , B , v ;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int t ; cin >> t ;
    while(t--){
        int a , b , k ; cin >> a >> b >> k ;
        if(k==1){
            if((a%b==0||b%a==0)&&a!=b) cout << "YES" << '\n' ;
            else cout << "NO" << '\n' ;
            continue ;
        }
        A.clear() ;
        for(int i=2 ; i*i<=a ; i++){
            while(a%i==0){
                a/=i ;
                A.push_back(i) ;
                //cout << i << ' ' ;
            }
        }
        if(a>1) A.push_back(a) ;
        //cout << a endl ;
        B.clear() ;
        for(int i=2 ; i*i<=b ; i++){
            while(b%i==0){
                b/=i ;
                B.push_back(i) ;
                //cout << i << ' ' ;
            }
        }
        if(b>1) B.push_back(b) ;
        //cout << endl ;
        if((A.size()+B.size())>=k) cout << "YES" << '\n' ;

        else cout << "NO" << '\n' ;
    }
}

### 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>

using namespace std ;
//it ain't much but it's honest work
const int MAX_N=2e5+10 ;
int a[MAX_N] ;

// just dont look

vector<int>A , B , v ;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int t ; cin >> t ;
    while(t--){
        int a , b , k ; cin >> a >> b >> k ;
        if(k==1){
            if((a%b==0||b%a==0)&&a!=b) cout << "YES" << '\n' ;
            else cout << "NO" << '\n' ;
            continue ;
        }
        A.clear() ;
        for(int i=2 ; i*i<=a ; i++){
            while(a%i==0){
                a/=i ;
                A.push_back(i) ;
                //cout << i << ' ' ;
            }
        }
        if(a>1) A.push_back(a) ;
        //cout << a endl ;
        B.clear() ;
        for(int i=2 ; i*i<=b ; i++){
            while(b%i==0){
                b/=i ;
                B.push_back(i) ;
                //cout << i << ' ' ;
            }
        }
        if(b>1) B.push_back(b) ;
        //cout << endl ;
        if((A.size()+B.size())>=k) cout << "YES" << '\n' ;

        else cout << "NO" << '\n' ;
    }
}

```