#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("sse4")
#pragma GCC target ("avx2")

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

#define int int64_t

namespace sieve{
    // segmented sieve magic lolz
    // all credit goes to: Kim Walisch and https://codeforces.com/blog/entry/75852?#comment-600840
    // credit to: https://github.com/kimwalisch/primesieve/wiki/Segmented-sieve-of-Eratosthenes
    #define byte unsigned char
    int count = 0; 
    vector<int> primes;
    void sieve(int lim) /// up_to 90e6 = 90.000.000 (get prime) | 168e6 = 168.000.000 (count only)
    {
        if (lim < 2) return ;
        int sqrt = std::sqrt(lim);
        int sieve_size = max((int)sqrt, (int)(1 << 15));
        int segment_size = sieve_size * 16;

        vector<byte> mark(sieve_size);
        vector<byte> is_prime(sqrt + 1, true);
        vector<int> seg_prime;
        vector<int> seg_multi;

        for (int i = 3; i <= sqrt; i += 2)
            if (is_prime[i])
                for (int j = i * i; j <= sqrt; j += i)
                    is_prime[j] = false;

        int reset[16];
        for (int i = 0; i < 8; ++i)
            reset[2 * i] = reset[2 * i + 1] = ~(1 << i);

        int popcnt[256];
        for (int i = 0; i < 256; ++i)
            popcnt[i] = __builtin_popcount(i);

        int s = 3;
        for (int low = 0; low <= lim; low += segment_size)
        {
            fill(mark.begin(), mark.end(), 0xff);
            int high = min(low + segment_size - 1, lim);
            sieve_size = (high - low) / 16 + 1;

            for (; s * s <= high; s += 2)
            {
                if (is_prime[s])
                {
                    seg_prime.push_back(s);
                    seg_multi.push_back(s * s - low);
                }
            }

            for (size_t i = 0; i < seg_prime.size(); ++i)
            {
                int j = seg_multi[i];
                for (int k = seg_prime[i] * 2; j < segment_size; j += k)
                    mark[j >> 4] &= reset[j % 16];

                seg_multi[i] = j - segment_size;
            }

            if (high == lim)
            {
                int bits = 0xff << ((lim % 16) + 1) / 2;
                mark[sieve_size - 1] &= ~bits;
            }
            
            for (int n = 0; n < sieve_size; n++)
            {
    //             count += popcnt[mark[n]]; continue;
                for (int i = 0; i < 8; i++)
                    if (mark[n] & (1 << i))
                        primes.push_back(low + n * 16 + i * 2 + 1);
            }
        }
    }
}

vector<int> p;

void test_case(int tc){
	int A, B, K; cin >> A >> B >> K;
	

	if(K == 1){
		if((B % A == 0 || A % B == 0) && (A != B)){
			cout << "YES" << "\n";
		} else{
			cout << "NO" << "\n";
		}
		return;
	}


	map<int, int> a_fact, b_fact;

	for(auto& prime : p){
		if(prime * prime > A){
			break;
		}
		while(A % prime == 0){
			a_fact[prime]++;
			A /= prime;
		}
	}

	if(A > 1){
		a_fact[A]++;
	}


	for(auto& prime : p){
		if(prime * prime > B){
			break;
		}
		while(B % prime == 0){
			b_fact[prime]++;
			B /= prime;
		}
	}

	if(B > 1){
		b_fact[B]++;
	}

	int a_tot = 0, b_tot = 0;

	for(auto& x : a_fact){
		if(x.first != 1){
			a_tot += (x.second);
		}
	}

	for(auto& x : b_fact){
		if(x.first != 1){
			b_tot += (x.second);
		}
	}

	if(a_tot + b_tot >= K){
		cout << "YES" << "\n";
	} else{
		cout << "NO" << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	sieve::sieve(31623);
	p = sieve::primes;
	p[0]++;


	int T=1; cin >> T;
	for(int tt = 1; tt <= T; ++tt){
		test_case(tt);
	}
}
### 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
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("sse4")
#pragma GCC target ("avx2")

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

#define int int64_t

namespace sieve{
    // segmented sieve magic lolz
    // all credit goes to: Kim Walisch and https://codeforces.com/blog/entry/75852?#comment-600840
    // credit to: https://github.com/kimwalisch/primesieve/wiki/Segmented-sieve-of-Eratosthenes
    #define byte unsigned char
    int count = 0; 
    vector<int> primes;
    void sieve(int lim) /// up_to 90e6 = 90.000.000 (get prime) | 168e6 = 168.000.000 (count only)
    {
        if (lim < 2) return ;
        int sqrt = std::sqrt(lim);
        int sieve_size = max((int)sqrt, (int)(1 << 15));
        int segment_size = sieve_size * 16;

        vector<byte> mark(sieve_size);
        vector<byte> is_prime(sqrt + 1, true);
        vector<int> seg_prime;
        vector<int> seg_multi;

        for (int i = 3; i <= sqrt; i += 2)
            if (is_prime[i])
                for (int j = i * i; j <= sqrt; j += i)
                    is_prime[j] = false;

        int reset[16];
        for (int i = 0; i < 8; ++i)
            reset[2 * i] = reset[2 * i + 1] = ~(1 << i);

        int popcnt[256];
        for (int i = 0; i < 256; ++i)
            popcnt[i] = __builtin_popcount(i);

        int s = 3;
        for (int low = 0; low <= lim; low += segment_size)
        {
            fill(mark.begin(), mark.end(), 0xff);
            int high = min(low + segment_size - 1, lim);
            sieve_size = (high - low) / 16 + 1;

            for (; s * s <= high; s += 2)
            {
                if (is_prime[s])
                {
                    seg_prime.push_back(s);
                    seg_multi.push_back(s * s - low);
                }
            }

            for (size_t i = 0; i < seg_prime.size(); ++i)
            {
                int j = seg_multi[i];
                for (int k = seg_prime[i] * 2; j < segment_size; j += k)
                    mark[j >> 4] &= reset[j % 16];

                seg_multi[i] = j - segment_size;
            }

            if (high == lim)
            {
                int bits = 0xff << ((lim % 16) + 1) / 2;
                mark[sieve_size - 1] &= ~bits;
            }
            
            for (int n = 0; n < sieve_size; n++)
            {
    //             count += popcnt[mark[n]]; continue;
                for (int i = 0; i < 8; i++)
                    if (mark[n] & (1 << i))
                        primes.push_back(low + n * 16 + i * 2 + 1);
            }
        }
    }
}

vector<int> p;

void test_case(int tc){
	int A, B, K; cin >> A >> B >> K;
	

	if(K == 1){
		if((B % A == 0 || A % B == 0) && (A != B)){
			cout << "YES" << "\n";
		} else{
			cout << "NO" << "\n";
		}
		return;
	}


	map<int, int> a_fact, b_fact;

	for(auto& prime : p){
		if(prime * prime > A){
			break;
		}
		while(A % prime == 0){
			a_fact[prime]++;
			A /= prime;
		}
	}

	if(A > 1){
		a_fact[A]++;
	}


	for(auto& prime : p){
		if(prime * prime > B){
			break;
		}
		while(B % prime == 0){
			b_fact[prime]++;
			B /= prime;
		}
	}

	if(B > 1){
		b_fact[B]++;
	}

	int a_tot = 0, b_tot = 0;

	for(auto& x : a_fact){
		if(x.first != 1){
			a_tot += (x.second);
		}
	}

	for(auto& x : b_fact){
		if(x.first != 1){
			b_tot += (x.second);
		}
	}

	if(a_tot + b_tot >= K){
		cout << "YES" << "\n";
	} else{
		cout << "NO" << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	sieve::sieve(31623);
	p = sieve::primes;
	p[0]++;


	int T=1; cin >> T;
	for(int tt = 1; tt <= T; ++tt){
		test_case(tt);
	}
}
```