#include <bits/stdc++.h>
#define ll long long
#define int long long
#define all(c) c.begin(), c.end()
#define unq(c)    \
    sort(all(c)); \
    c.resize(unique(all(c)) - c.begin())
#define f first
#define s second
using namespace std;
template <class T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    for (auto i : v) {
        os << i << ' ';
    }
    return os << '\n';
}
template <class T>
inline std::istream& operator>>(std::istream& in, std::vector<T>& v) {
    for (auto& i : v) {
        cin >> i;
    }
    return in;
}

vector<int> pr;
 
vector<bool> st(32000);
 
void seive()
{
	pr.push_back(2);
	st[2] = 0;
	for(int i=4;i<=32000;i+=2) st[i] = 1;
	for(int i=3;i<32000;i+=2)
	{
		if(st[i]==0)
		{
			pr.push_back(i);
			for(int j= i*i ; j<=32000; j+=i) st[j] = 1;
		}
	}
}
bool CF = true;
int fact(int n)
{
	int ans = 0;
	for(auto i :pr)
	{
		if(i*i>n) break;
		while(n%i==0)
		{
			n /= i;
			ans++;
		}
	}
	if(n>1) ans++;
	return ans ;
}

auto solve() -> void {
    int a, b, k;
    cin >> a >> b >> k;
    int s =fact(a) +fact(b);
    if(k > s){
        cout << "NO\n";
        return;
    }
    if(k == 0){
        if(a != b){
            cout << "NO\n";
        }else cout << "YES\n";
        return;
    }
    if(a > b) swap(a, b);
    if(k == 1){
        if((a == b) || (b % a != 0)){
            cout << "NO\n";
        }else cout << "YES\n";
        return;
    }
    if (k == 2){
        cout << "YES\n";
        return;
    }
    if(k > 2){
        cout << "YES\n";
        return;
    }
}
auto main() -> signed{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    seive();
    int t = 1;
    if (CF) cin >> t;
    while (t--) solve();
    return 0;
}

### Prompt

Develop a solution in CPP 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 ll long long
#define int long long
#define all(c) c.begin(), c.end()
#define unq(c)    \
    sort(all(c)); \
    c.resize(unique(all(c)) - c.begin())
#define f first
#define s second
using namespace std;
template <class T>
inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    for (auto i : v) {
        os << i << ' ';
    }
    return os << '\n';
}
template <class T>
inline std::istream& operator>>(std::istream& in, std::vector<T>& v) {
    for (auto& i : v) {
        cin >> i;
    }
    return in;
}

vector<int> pr;
 
vector<bool> st(32000);
 
void seive()
{
	pr.push_back(2);
	st[2] = 0;
	for(int i=4;i<=32000;i+=2) st[i] = 1;
	for(int i=3;i<32000;i+=2)
	{
		if(st[i]==0)
		{
			pr.push_back(i);
			for(int j= i*i ; j<=32000; j+=i) st[j] = 1;
		}
	}
}
bool CF = true;
int fact(int n)
{
	int ans = 0;
	for(auto i :pr)
	{
		if(i*i>n) break;
		while(n%i==0)
		{
			n /= i;
			ans++;
		}
	}
	if(n>1) ans++;
	return ans ;
}

auto solve() -> void {
    int a, b, k;
    cin >> a >> b >> k;
    int s =fact(a) +fact(b);
    if(k > s){
        cout << "NO\n";
        return;
    }
    if(k == 0){
        if(a != b){
            cout << "NO\n";
        }else cout << "YES\n";
        return;
    }
    if(a > b) swap(a, b);
    if(k == 1){
        if((a == b) || (b % a != 0)){
            cout << "NO\n";
        }else cout << "YES\n";
        return;
    }
    if (k == 2){
        cout << "YES\n";
        return;
    }
    if(k > 2){
        cout << "YES\n";
        return;
    }
}
auto main() -> signed{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    seive();
    int t = 1;
    if (CF) cin >> t;
    while (t--) solve();
    return 0;
}

```