//#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int N = 1e5+5;
const int mod = 1e9+7;
int prime[N],cnt;
bool st[N];
void get_prime(int n)
{
	st[0]=st[1]=true;
	for(int i=2; i<=n; i++) {
		if(!st[i])prime[cnt++]=i;
		for(int j=0; prime[j]<=n/i; j++) {
			st[i*prime[j]]=true;
			if(i%prime[j]==0)break;
		}
	}
}
int T,n,m;
int main()
{
	get_prime(N-1);
	scanf("%d",&T);
	while(T--) {
		int a,b,k,c1,c2;
		c1=c2=0;
		scanf("%d%d%d",&a,&b,&k);
		if(k==1) {
			if(a==b)puts("NO");
			else {
				if(a%b&&b%a)puts("NO");
				else puts("YES");
			}
			continue;
		}
		for(int i=0; i<cnt; i++) {
			if(a==1)break;
			while(a%prime[i]==0) {
				c1++;
				a/=prime[i];
			}
		}
		if(a>1)c1++;
		for(int i=0; i<cnt; i++) {
			if(b==1)break;
			while(b%prime[i]==0) {
				c2++;
				b/=prime[i];
			}
		}
		if(b>1)c2++;
		puts(c1+c2>=k?"YES":"NO");
	}
	return 0;
}
### Prompt

Please formulate 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
//#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int N = 1e5+5;
const int mod = 1e9+7;
int prime[N],cnt;
bool st[N];
void get_prime(int n)
{
	st[0]=st[1]=true;
	for(int i=2; i<=n; i++) {
		if(!st[i])prime[cnt++]=i;
		for(int j=0; prime[j]<=n/i; j++) {
			st[i*prime[j]]=true;
			if(i%prime[j]==0)break;
		}
	}
}
int T,n,m;
int main()
{
	get_prime(N-1);
	scanf("%d",&T);
	while(T--) {
		int a,b,k,c1,c2;
		c1=c2=0;
		scanf("%d%d%d",&a,&b,&k);
		if(k==1) {
			if(a==b)puts("NO");
			else {
				if(a%b&&b%a)puts("NO");
				else puts("YES");
			}
			continue;
		}
		for(int i=0; i<cnt; i++) {
			if(a==1)break;
			while(a%prime[i]==0) {
				c1++;
				a/=prime[i];
			}
		}
		if(a>1)c1++;
		for(int i=0; i<cnt; i++) {
			if(b==1)break;
			while(b%prime[i]==0) {
				c2++;
				b/=prime[i];
			}
		}
		if(b>1)c2++;
		puts(c1+c2>=k?"YES":"NO");
	}
	return 0;
}
```