#include<bits/stdc++.h>
#define rep(i,st,en) for(int i=st;i<=en;i++)
#define REP(i,st,en) for(int i=st;i>=en;i--)
#define con continue
#define endl printf("\n");
using namespace std;
typedef long long ll;
int t,a,b,k,cnt1,cnt2;

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&a,&b,&k);
		int x=a,y=b;
		if(x>y)swap(x,y),swap(a,b);
		cnt1=cnt2=0;
		for(int i=2;i*i<=a;i++)
			while(a%i==0)
				a/=i,cnt1++;
		if(a>1)
			cnt1++;
		for(int i=2;i*i<=b;i++)
			while(b%i==0)
				b/=i,cnt2++;
		if(b>1)cnt2++;
		if(cnt1+cnt2<k)
		{
			printf("No\n");
			con;
		}		
		if(x==y&&k==1)
		{
			printf("No\n");
			con;
		}
		if(x!=y&&y/x*x!=y&&k<2)
		{
			printf("No\n");
			con;
		}
		printf("Yes");
		endl;
		
	}
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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>
#define rep(i,st,en) for(int i=st;i<=en;i++)
#define REP(i,st,en) for(int i=st;i>=en;i--)
#define con continue
#define endl printf("\n");
using namespace std;
typedef long long ll;
int t,a,b,k,cnt1,cnt2;

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&a,&b,&k);
		int x=a,y=b;
		if(x>y)swap(x,y),swap(a,b);
		cnt1=cnt2=0;
		for(int i=2;i*i<=a;i++)
			while(a%i==0)
				a/=i,cnt1++;
		if(a>1)
			cnt1++;
		for(int i=2;i*i<=b;i++)
			while(b%i==0)
				b/=i,cnt2++;
		if(b>1)cnt2++;
		if(cnt1+cnt2<k)
		{
			printf("No\n");
			con;
		}		
		if(x==y&&k==1)
		{
			printf("No\n");
			con;
		}
		if(x!=y&&y/x*x!=y&&k<2)
		{
			printf("No\n");
			con;
		}
		printf("Yes");
		endl;
		
	}
	return 0;
}
```