// 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19   20  21  22  23  24 25 26 27 28 29 30 31 
 // 1  1  1  1  1  1  1  1  1   2   1   1   1   1    1  1   1   1    2    1   1   1   1  1  1  1  1  1  2  1
 // 1  2  3  4  5  6  7  8  9   10  11  12  13  14  15  16  17  18  19    20  21  22  23 24 25 26 27 28 29 30


					#include <bits/stdc++.h>
					#define pb push_back
					#define mp make_pair
					const int mod = 1e9 + 7;
					
					using namespace std;
									
					#define TRACE
					#ifdef TRACE
					    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
					    template <typename Arg1>
					    void __f(const char* name, Arg1&& arg1){
					        cerr << name << " : " << arg1 << endl;
					    }
					    template <typename Arg1, typename... Args>
					    void __f(const char* names, Arg1&& arg1, Args&&... args){
					        const char* comma = strchr(names + 1, ',');
					        cerr.write(names, comma - names) << " : " << arg1<<" | ";
					        __f(comma+1, args...);
					    }
					#else
					    #define trace(...)
					#endif
					
					
					int go(int n){
						int how = 0;
						// assert(n > 1);
						
					    while (n % 2 == 0)
					    {
					        // cout << 2 << " ";
					        // p.insert(2);
					        // return 2;
					        how++;
					        n = n/2;
					    }
					 
					    // n must be odd at this point. So we can skip
					    // one element (Note i = i +2)
					    for (int i = 3; i <= sqrt(n); i = i + 2)
					    {
					        // While i divides n, print i and divide n
					        while (n % i == 0)
					        {
					            // cout << i << " ";
					            // p.insert(i);
					            // return i;
					            how++;
					            n = n/i;
					        }
					    }
					 
					    // This condition is to handle the case when n
					    // is a prime number greater than 2
					    if (n > 2){
					        // cout << n << " ";
					        // p.insert(n);
					        // return n;
					        how++;
					        
					    }
					    return how;
					}	
															
					void solve(void){
						int a, b, k;
						cin >> a >> b >> k;
						
						if(k > 70){
							cout << "NO" << endl;
							return;
						}
						if(a==b){
							if(k > 1 and 2 * go(a) >= k){
								cout << "YES" << endl;
								return;
								
							}
							cout << "NO" << endl;
							return;
						}
						for(int x = 1; x < 2; x++){
							if(x>1)
							break;
							int A = a / x;
							int B = b / x;
							int aa = go(A);
							int bb = go(B);
							if(k >= 1 + (max(A, B) % min(A, B) != 0) and k <= aa + bb){
								cout << "YES" << endl;
								return;
							}
						}
						cout << "NO" << endl;
					}
					
					signed main() {
					int t = 1; 
					cin >> t;
					while(t--){
					    solve();
					}	
					
					    return 0LL;
					}
### Prompt

Your task is to create a cpp solution to 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
// 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19   20  21  22  23  24 25 26 27 28 29 30 31 
 // 1  1  1  1  1  1  1  1  1   2   1   1   1   1    1  1   1   1    2    1   1   1   1  1  1  1  1  1  2  1
 // 1  2  3  4  5  6  7  8  9   10  11  12  13  14  15  16  17  18  19    20  21  22  23 24 25 26 27 28 29 30


					#include <bits/stdc++.h>
					#define pb push_back
					#define mp make_pair
					const int mod = 1e9 + 7;
					
					using namespace std;
									
					#define TRACE
					#ifdef TRACE
					    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
					    template <typename Arg1>
					    void __f(const char* name, Arg1&& arg1){
					        cerr << name << " : " << arg1 << endl;
					    }
					    template <typename Arg1, typename... Args>
					    void __f(const char* names, Arg1&& arg1, Args&&... args){
					        const char* comma = strchr(names + 1, ',');
					        cerr.write(names, comma - names) << " : " << arg1<<" | ";
					        __f(comma+1, args...);
					    }
					#else
					    #define trace(...)
					#endif
					
					
					int go(int n){
						int how = 0;
						// assert(n > 1);
						
					    while (n % 2 == 0)
					    {
					        // cout << 2 << " ";
					        // p.insert(2);
					        // return 2;
					        how++;
					        n = n/2;
					    }
					 
					    // n must be odd at this point. So we can skip
					    // one element (Note i = i +2)
					    for (int i = 3; i <= sqrt(n); i = i + 2)
					    {
					        // While i divides n, print i and divide n
					        while (n % i == 0)
					        {
					            // cout << i << " ";
					            // p.insert(i);
					            // return i;
					            how++;
					            n = n/i;
					        }
					    }
					 
					    // This condition is to handle the case when n
					    // is a prime number greater than 2
					    if (n > 2){
					        // cout << n << " ";
					        // p.insert(n);
					        // return n;
					        how++;
					        
					    }
					    return how;
					}	
															
					void solve(void){
						int a, b, k;
						cin >> a >> b >> k;
						
						if(k > 70){
							cout << "NO" << endl;
							return;
						}
						if(a==b){
							if(k > 1 and 2 * go(a) >= k){
								cout << "YES" << endl;
								return;
								
							}
							cout << "NO" << endl;
							return;
						}
						for(int x = 1; x < 2; x++){
							if(x>1)
							break;
							int A = a / x;
							int B = b / x;
							int aa = go(A);
							int bb = go(B);
							if(k >= 1 + (max(A, B) % min(A, B) != 0) and k <= aa + bb){
								cout << "YES" << endl;
								return;
							}
						}
						cout << "NO" << endl;
					}
					
					signed main() {
					int t = 1; 
					cin >> t;
					while(t--){
					    solve();
					}	
					
					    return 0LL;
					}
```