#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 2;

int a[N];
int prime[N], vis[N], cnt;
ll ans;
vector<int> pa, pb;

void init(int n) {
	for (int i = 2; i <= n; ++i) {
		if (!vis[i]) prime[cnt++] = i;
		for (int j = 0; j < cnt && i * prime[j] <= n; ++j) {
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) {
				break;
			}
		}
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	init(100000);
	int T;
	scanf("%d", &T);
	while(T--) {
		pa.clear(); pb.clear();
		int a, b, k;
		scanf("%d%d%d", &a, &b, &k);
		int a_ = a, b_ = b;
		for (int i = 0; prime[i] * prime[i] <= a; ++i) {
			if (a % prime[i] == 0) {
				while(a % prime[i] == 0) {
					a /= prime[i];
					pa.push_back(prime[i]);
				}
			}
		}
		if (a != 1) {
			pa.push_back(a);
		}
		for (int i = 0; prime[i] * prime[i] <= b; ++i) {
			if (b % prime[i] == 0) {
				while(b % prime[i] == 0) {
					b /= prime[i];
					pb.push_back(prime[i]);
				}
			}
		}
		if (b != 1) {
			pb.push_back(b);
		}
		int all = (int)pa.size() + (int)pb.size();
		if (k == 1 && (a_ % b_ == 0 || b_ % a_ == 0) && a_ != b_) {
			printf("YES\n");
		}
		else if (k == 1 && all > 1) {
			printf("NO\n");
		}
		else if (all >= k) {
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
}
### Prompt

Please create a solution in CPP 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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 2;

int a[N];
int prime[N], vis[N], cnt;
ll ans;
vector<int> pa, pb;

void init(int n) {
	for (int i = 2; i <= n; ++i) {
		if (!vis[i]) prime[cnt++] = i;
		for (int j = 0; j < cnt && i * prime[j] <= n; ++j) {
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) {
				break;
			}
		}
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	init(100000);
	int T;
	scanf("%d", &T);
	while(T--) {
		pa.clear(); pb.clear();
		int a, b, k;
		scanf("%d%d%d", &a, &b, &k);
		int a_ = a, b_ = b;
		for (int i = 0; prime[i] * prime[i] <= a; ++i) {
			if (a % prime[i] == 0) {
				while(a % prime[i] == 0) {
					a /= prime[i];
					pa.push_back(prime[i]);
				}
			}
		}
		if (a != 1) {
			pa.push_back(a);
		}
		for (int i = 0; prime[i] * prime[i] <= b; ++i) {
			if (b % prime[i] == 0) {
				while(b % prime[i] == 0) {
					b /= prime[i];
					pb.push_back(prime[i]);
				}
			}
		}
		if (b != 1) {
			pb.push_back(b);
		}
		int all = (int)pa.size() + (int)pb.size();
		if (k == 1 && (a_ % b_ == 0 || b_ % a_ == 0) && a_ != b_) {
			printf("YES\n");
		}
		else if (k == 1 && all > 1) {
			printf("NO\n");
		}
		else if (all >= k) {
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
}
```