#include<bits/stdc++.h>
using namespace std;

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
void init_code(){
fast_io;
#ifndef ONLINE_JUDGE
freopen("INPUT.txt", "r", stdin);
freopen("OUTPUT.txt", "w", stdout);
freopen("ERROR.txt", "w", stderr);
#endif
}
void _print(int a) {
	cerr<<a;
}
void _print(char a){
	cerr<<a;
} 
void _print( string a) {
	cerr<<a;
}
void _print(long long a) {
	cerr<<a;
}
void _print(bool a) {
	cerr<<a;
}
template <class T>void _print(vector<T> v1){
	cerr<<"[";
	for(T i: v1)
	{
		_print(i);
		cerr<<" ";
	}
		cerr<<"]";
}
#ifndef ONLINE_JUDGE
#define debug(x) cerr <<#x<<" ";_print(x);cerr<<"\n";  
#else
#define debug(x)   
#endif 
//--------------------------------------------------------------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------------------------------------------------------------



#define ll long long
#define M 1e9+7
#define pb push_back
#define all(x) x.begin(),x.end()
typedef vector<int> vi;
vector<ll> sieve(int n)
{
	int*arr = new int[n + 1](); 
	vector<ll> vect;
	for (int i = 2; i <= n; i++)
		if (arr[i] == 0) 
			{
				vect.push_back(i);
			for (int j = 2 * i; j <= n; j += i)
				arr[j] = 1;
		    }
		 return vect;
}


vector<ll> v1 = sieve(36123);
 
ll steps(ll a) {
	ll count1 = 0;
	for (auto i : v1) {
		if (i > a)
			break;
		if (a % i == 0) {
			while (a % i == 0) {
				count1++;
				a /= i;
			}
		}
	}
	if (a > 1)
		count1++;
	return count1;
}
void solve() {
	int t;
	cin >> t;
	while (t--) {
		ll a, b, k;
		cin >> a >> b >> k;
		if (a == b) {
			if (k == 1) {
				cout << "No" << "\n";
			} else {
				ll steps1 = steps(a);
				ll steps2 = steps1;
				if (steps1 + steps2 >= k) {
					cout << "Yes" << "\n";
				} else {
					cout << "No" << "\n";
				}
			}
			continue;
		}
		if ((a % b == 0) || (b % a == 0)) {
			if (b % a == 0) {
				swap(a, b);
			}
			ll steps1 = steps(a);
			ll steps2 = steps(b);
			if (steps2 + steps1 >= k) {
				cout << "Yes" << "\n";
			} else {
				cout << "No" << "\n";
			}
			continue;
		}
		if (k == 1) {
			cout << "No" << "\n";
			continue;
		}
		ll steps1 = steps(a);
		ll steps2 = steps(b);
		if (steps2 + steps1 >= k) {
			cout << "Yes" << "\n";
		} else {
			cout << "No" << "\n";
		}
	}
}
int main() 
{
	init_code();
	solve();

}
### 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<bits/stdc++.h>
using namespace std;

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
void init_code(){
fast_io;
#ifndef ONLINE_JUDGE
freopen("INPUT.txt", "r", stdin);
freopen("OUTPUT.txt", "w", stdout);
freopen("ERROR.txt", "w", stderr);
#endif
}
void _print(int a) {
	cerr<<a;
}
void _print(char a){
	cerr<<a;
} 
void _print( string a) {
	cerr<<a;
}
void _print(long long a) {
	cerr<<a;
}
void _print(bool a) {
	cerr<<a;
}
template <class T>void _print(vector<T> v1){
	cerr<<"[";
	for(T i: v1)
	{
		_print(i);
		cerr<<" ";
	}
		cerr<<"]";
}
#ifndef ONLINE_JUDGE
#define debug(x) cerr <<#x<<" ";_print(x);cerr<<"\n";  
#else
#define debug(x)   
#endif 
//--------------------------------------------------------------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------------------------------------------------------------



#define ll long long
#define M 1e9+7
#define pb push_back
#define all(x) x.begin(),x.end()
typedef vector<int> vi;
vector<ll> sieve(int n)
{
	int*arr = new int[n + 1](); 
	vector<ll> vect;
	for (int i = 2; i <= n; i++)
		if (arr[i] == 0) 
			{
				vect.push_back(i);
			for (int j = 2 * i; j <= n; j += i)
				arr[j] = 1;
		    }
		 return vect;
}


vector<ll> v1 = sieve(36123);
 
ll steps(ll a) {
	ll count1 = 0;
	for (auto i : v1) {
		if (i > a)
			break;
		if (a % i == 0) {
			while (a % i == 0) {
				count1++;
				a /= i;
			}
		}
	}
	if (a > 1)
		count1++;
	return count1;
}
void solve() {
	int t;
	cin >> t;
	while (t--) {
		ll a, b, k;
		cin >> a >> b >> k;
		if (a == b) {
			if (k == 1) {
				cout << "No" << "\n";
			} else {
				ll steps1 = steps(a);
				ll steps2 = steps1;
				if (steps1 + steps2 >= k) {
					cout << "Yes" << "\n";
				} else {
					cout << "No" << "\n";
				}
			}
			continue;
		}
		if ((a % b == 0) || (b % a == 0)) {
			if (b % a == 0) {
				swap(a, b);
			}
			ll steps1 = steps(a);
			ll steps2 = steps(b);
			if (steps2 + steps1 >= k) {
				cout << "Yes" << "\n";
			} else {
				cout << "No" << "\n";
			}
			continue;
		}
		if (k == 1) {
			cout << "No" << "\n";
			continue;
		}
		ll steps1 = steps(a);
		ll steps2 = steps(b);
		if (steps2 + steps1 >= k) {
			cout << "Yes" << "\n";
		} else {
			cout << "No" << "\n";
		}
	}
}
int main() 
{
	init_code();
	solve();

}
```