#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cmath>
using namespace std;
int t;//t组数据
int a,b,k;
int m_i,m_a;
int gcd(int a,int b){
	if(!b){
		return a;
	}
	gcd(b,a%b);
}
int f_i(int a){
	int n_n=0;
	int a_a=a;
	for(int i=2;i*i<=a_a;i++){
		if(a==1)break;
		if(a%i==0){
			while(a%i==0){
				a/=i;n_n++;
			}
		}
	}
    if(a>1)n_n++;
	return n_n;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d %d %d",&a,&b,&k);
		if(a<b)swap(a,b);
		int g_c=gcd(a,b);
		if((g_c==a||g_c==b)&&a!=b)m_i=1;
		else m_i=2;
		m_a=2*f_i(g_c)+f_i(a/g_c)+f_i(b/g_c);
		if(k>=m_i&&k<=m_a)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0; 
}
### Prompt

Create a solution in Cpp for 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<iostream>
#include<cstdio>
#include<algorithm> 
#include<cmath>
using namespace std;
int t;//t组数据
int a,b,k;
int m_i,m_a;
int gcd(int a,int b){
	if(!b){
		return a;
	}
	gcd(b,a%b);
}
int f_i(int a){
	int n_n=0;
	int a_a=a;
	for(int i=2;i*i<=a_a;i++){
		if(a==1)break;
		if(a%i==0){
			while(a%i==0){
				a/=i;n_n++;
			}
		}
	}
    if(a>1)n_n++;
	return n_n;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d %d %d",&a,&b,&k);
		if(a<b)swap(a,b);
		int g_c=gcd(a,b);
		if((g_c==a||g_c==b)&&a!=b)m_i=1;
		else m_i=2;
		m_a=2*f_i(g_c)+f_i(a/g_c)+f_i(b/g_c);
		if(k>=m_i&&k<=m_a)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0; 
}
```