#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1e9+7
#define c 100005
#define debug(x) cout << #x << " is " << x << endl;
#define de2(x,y) cout << #x << " is " << x << " " << #y << " is " << y << endl;

void solve(int a, int b, int k){
	int t=0;
	int n = (a%b==0 || b%a==0)?1:2;
	n = (a==b)?0:n;
	for (int i=2; i*i<=a; ++i)
		if (a%i==0){
			while (a%i==0){
				a/=i;
				t++;
			}
		}
	if (a>1) t++;
	for (int i=2; i*i<=b; ++i)
		if (b%i==0){
			while (b%i==0){
				b/=i;
				t++;
			}
		}
	if (b>1) t++;
	if ((t>=k && k>=n && k!=1) || (t>=k && k==1 && n==1)) cout << "YES" << endl;
	else cout << "NO" << endl;
}
	

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	while (tc--){
		int a, b, k;
		cin >> a >> b >> k;
		solve(a,b,k);
	}	
	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>
using namespace std;
typedef long long ll;
#define mod 1e9+7
#define c 100005
#define debug(x) cout << #x << " is " << x << endl;
#define de2(x,y) cout << #x << " is " << x << " " << #y << " is " << y << endl;

void solve(int a, int b, int k){
	int t=0;
	int n = (a%b==0 || b%a==0)?1:2;
	n = (a==b)?0:n;
	for (int i=2; i*i<=a; ++i)
		if (a%i==0){
			while (a%i==0){
				a/=i;
				t++;
			}
		}
	if (a>1) t++;
	for (int i=2; i*i<=b; ++i)
		if (b%i==0){
			while (b%i==0){
				b/=i;
				t++;
			}
		}
	if (b>1) t++;
	if ((t>=k && k>=n && k!=1) || (t>=k && k==1 && n==1)) cout << "YES" << endl;
	else cout << "NO" << endl;
}
	

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	while (tc--){
		int a, b, k;
		cin >> a >> b >> k;
		solve(a,b,k);
	}	
	return 0;
}



```