#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define vl vector<ll>
#define vvl vector<vl>
#define vld vector<ld>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define rep(s, l, r) for (int s = l; s < r; s++)
#define per(s, r, l) for (int s = r - 1; s >= l; s--)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
using namespace std;
template<class T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> void setmax(T& a, T b) { a = max(a, b); };
template<typename T> void setmin(T& a, T b) { a = min(a, b); };
template<typename T> bool in(T lo, T v, T hi) { return lo <= v && v <= hi; };
struct timestamp {
  string algo;
  ld A, B;

  timestamp(string _algo) {
    algo = _algo;
    A = B = clock();
  }
  void print() {
    ld B_ = clock();
    ld section = (B_ - B) / CLOCKS_PER_SEC;
    ld cumulative = (B_ - A) / CLOCKS_PER_SEC;
    cout << algo << " profile(seconds): section: " << section << " cumulative: " << cumulative << endl << flush;
    B = B_;
  }
};

template<ll MOD>
struct ModInt {
	ll x = 0;
	ModInt() { x = 0; }
	ModInt(ll _x) { 
		x = _x; 
		if (x >= MOD || x <= -MOD) x %= MOD;
		if (x < 0) x += MOD;
	}
	friend ModInt operator+(ModInt a, ModInt b) {
		return ModInt(a.x + b.x);
	}
	friend ModInt operator-(ModInt a, ModInt b) {
		return ModInt(a.x - b.x);
	}
	friend ModInt operator*(ModInt a, ModInt b) {
		return ModInt(a.x * b.x);
	}
	friend ModInt operator/(ModInt a, ModInt b) {
		return a * inv(b);
	}
	friend ModInt operator+=(ModInt &a, ModInt b) {
		return a = a + b;
	}
	friend ModInt power(ModInt a, ll b) {
		if (b == 0) return 1;
		ModInt c = power(a, b / 2);
		return c * c * ((b & 1) ? a : 1);
	}
	friend ModInt inv(ModInt a) {
		// this only works for nonzero elements
		return power(a, MOD - 2);
	}
	friend ostream& operator<<(ostream &os, const ModInt &a) {
		os << a.x;
		return os;
	}
	friend istream& operator>>(istream &is, ModInt &a) {
		ll y; is >> y; a = ModInt(y);
		return is;
	}
};

using mint = ModInt<1000000007>;
using vm = vector<mint>;
using vvm = vector<vm>;

vl primes;

void precalc() {
	const int M = 50000;
	vi x(M, 1);
	for (int i = 2; i < M; i++) {
		if (x[i]) {
			primes.pb(i);
			for (int j = 2 * i; j < M; j += i) 
				x[j] = 0;
		}
	}
}

struct Solution {
	ll gcd(ll a, ll b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	int numPr(int x) {
		if (x == 1) return 0;
		int cnt = 0;
		for (int p : primes) {
			while (x % p == 0) {
				cnt++;
				x /= p;
			}
			if (p * p > x) break;
		}
		if (x > 1) cnt++;
		return cnt;
	}

	void solve() {
		ll a, b, k;
		cin >> a >> b >> k;
		bool can;
		if (k == 1) {
			can = (a % b == 0 || b % a == 0) && (a != b);
		} else {
			ll x = numPr(a);
			ll y = numPr(b);
			if (x + y < k) {
				can = false;
			} else {
				can = true;
			}
		}
		cout << (can ? "YES" : "NO") << endl;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	precalc();
	int t = 1;
	cin >> t;
	while (t--) {
		Solution s;
		s.solve();
	}

  return 0;
}

### Prompt

Generate a Cpp solution to 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>
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define vl vector<ll>
#define vvl vector<vl>
#define vld vector<ld>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define rep(s, l, r) for (int s = l; s < r; s++)
#define per(s, r, l) for (int s = r - 1; s >= l; s--)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
using namespace std;
template<class T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> void setmax(T& a, T b) { a = max(a, b); };
template<typename T> void setmin(T& a, T b) { a = min(a, b); };
template<typename T> bool in(T lo, T v, T hi) { return lo <= v && v <= hi; };
struct timestamp {
  string algo;
  ld A, B;

  timestamp(string _algo) {
    algo = _algo;
    A = B = clock();
  }
  void print() {
    ld B_ = clock();
    ld section = (B_ - B) / CLOCKS_PER_SEC;
    ld cumulative = (B_ - A) / CLOCKS_PER_SEC;
    cout << algo << " profile(seconds): section: " << section << " cumulative: " << cumulative << endl << flush;
    B = B_;
  }
};

template<ll MOD>
struct ModInt {
	ll x = 0;
	ModInt() { x = 0; }
	ModInt(ll _x) { 
		x = _x; 
		if (x >= MOD || x <= -MOD) x %= MOD;
		if (x < 0) x += MOD;
	}
	friend ModInt operator+(ModInt a, ModInt b) {
		return ModInt(a.x + b.x);
	}
	friend ModInt operator-(ModInt a, ModInt b) {
		return ModInt(a.x - b.x);
	}
	friend ModInt operator*(ModInt a, ModInt b) {
		return ModInt(a.x * b.x);
	}
	friend ModInt operator/(ModInt a, ModInt b) {
		return a * inv(b);
	}
	friend ModInt operator+=(ModInt &a, ModInt b) {
		return a = a + b;
	}
	friend ModInt power(ModInt a, ll b) {
		if (b == 0) return 1;
		ModInt c = power(a, b / 2);
		return c * c * ((b & 1) ? a : 1);
	}
	friend ModInt inv(ModInt a) {
		// this only works for nonzero elements
		return power(a, MOD - 2);
	}
	friend ostream& operator<<(ostream &os, const ModInt &a) {
		os << a.x;
		return os;
	}
	friend istream& operator>>(istream &is, ModInt &a) {
		ll y; is >> y; a = ModInt(y);
		return is;
	}
};

using mint = ModInt<1000000007>;
using vm = vector<mint>;
using vvm = vector<vm>;

vl primes;

void precalc() {
	const int M = 50000;
	vi x(M, 1);
	for (int i = 2; i < M; i++) {
		if (x[i]) {
			primes.pb(i);
			for (int j = 2 * i; j < M; j += i) 
				x[j] = 0;
		}
	}
}

struct Solution {
	ll gcd(ll a, ll b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	int numPr(int x) {
		if (x == 1) return 0;
		int cnt = 0;
		for (int p : primes) {
			while (x % p == 0) {
				cnt++;
				x /= p;
			}
			if (p * p > x) break;
		}
		if (x > 1) cnt++;
		return cnt;
	}

	void solve() {
		ll a, b, k;
		cin >> a >> b >> k;
		bool can;
		if (k == 1) {
			can = (a % b == 0 || b % a == 0) && (a != b);
		} else {
			ll x = numPr(a);
			ll y = numPr(b);
			if (x + y < k) {
				can = false;
			} else {
				can = true;
			}
		}
		cout << (can ? "YES" : "NO") << endl;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	precalc();
	int t = 1;
	cin >> t;
	while (t--) {
		Solution s;
		s.solve();
	}

  return 0;
}

```