#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
#define tr(container,it) for(auto it=container.begin();it!=container.end();it++)

using pi = pair <int, int>;
using vi = vector <int>;
using vvi = vector<vector<int> >;
//const int infl = 9e18;
int mod = 1e9 + 7;

long long int bs1(long long int a[], long long int n, long long int l, long long int r, long long int k)
{
	if (l > r)
		return l;
	long long int m = (l + r) / 2;
	if (a[m] == k) return m;
	else if (a[m] > k) return bs1(a, n, l, m - 1, k);
	else return bs1(a, n, m + 1, r, k);
}

long long int bs2(long long int a[], long long int n, long long int l, long long int r, long long int k)
{
	if (l > r)
		return r;
	long long int m = (l + r) / 2;
	if (a[m] == k) return m;
	else if (a[m] > k) return bs1(a, n, l, m - 1, k);
	else return bs1(a, n, m + 1, r, k);
}


int gcd(int a, int b)
{
	if (a < b)
	{
		swap(a, b);
	}
	if (a == 1 || b == 1)
	{
		return 1;
	}
	if (a == 0 || b == 0)
	{
		return max(a, b);
	}
	if (a == b)
	{
		return a;
	}
	else
	{
		return gcd(b, a % b);
	}
}

int mul(int x, int y)
{
	int one = 1;
	return (x * one * y) % mod;
}

/*int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}*/

/*int inv(int x)
{
    return binpow(x, mod - 2);
}*/

/*int divide(int x, int y)
{
    return mul(x, inv(y));
}*/


/*int  fact[200005];

void precalc()
{
    fact[0] = 1;
    for(int i = 1; i < 200005; i++)
    {
        fact[i] = mul(fact[i - 1], i);
    }
      //fact[i]=fact[i-1]*i;
}*/

int pf(int a)
{
	int count = 0;
	while (a % 2 == 0)
	{
		a /= 2;
		count++;
	}
	for (int i = 3; i <= sqrt(a); i += 2)
	{
		while (a % i == 0)
		{
			a /= i;
			count++;
		}
	}
	if (a != 1)
	{
		return count + 1;
	}
	return count;
}

signed main()
{
	int t, a, b, k;
	//calc();
	cin >> t;
	while (t--)
	{
		cin >> a >> b >> k;
		if ((a == b && k == 1) || (a == 1 && b == 1))
		{
			cout << "NO" << endl;
			continue;
		}
		else if (k == 1)
		{
			if (a % b == 0 || b % a == 0)
			{
				cout << "YES" << endl;
			}
			else
			{
				cout << "NO" << endl;
			}
		}
		else
		{	int x = pf(a); int y = pf(b);
			//cout << x << " " << y << endl;
			if (x + y >= k)
			{
				cout << "YES" << endl;
			}
			else
			{
				cout << "NO" << endl;
			}
		}
	}
}
### Prompt

Construct a CPP code solution to the problem outlined:

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 int long long
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
#define tr(container,it) for(auto it=container.begin();it!=container.end();it++)

using pi = pair <int, int>;
using vi = vector <int>;
using vvi = vector<vector<int> >;
//const int infl = 9e18;
int mod = 1e9 + 7;

long long int bs1(long long int a[], long long int n, long long int l, long long int r, long long int k)
{
	if (l > r)
		return l;
	long long int m = (l + r) / 2;
	if (a[m] == k) return m;
	else if (a[m] > k) return bs1(a, n, l, m - 1, k);
	else return bs1(a, n, m + 1, r, k);
}

long long int bs2(long long int a[], long long int n, long long int l, long long int r, long long int k)
{
	if (l > r)
		return r;
	long long int m = (l + r) / 2;
	if (a[m] == k) return m;
	else if (a[m] > k) return bs1(a, n, l, m - 1, k);
	else return bs1(a, n, m + 1, r, k);
}


int gcd(int a, int b)
{
	if (a < b)
	{
		swap(a, b);
	}
	if (a == 1 || b == 1)
	{
		return 1;
	}
	if (a == 0 || b == 0)
	{
		return max(a, b);
	}
	if (a == b)
	{
		return a;
	}
	else
	{
		return gcd(b, a % b);
	}
}

int mul(int x, int y)
{
	int one = 1;
	return (x * one * y) % mod;
}

/*int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}*/

/*int inv(int x)
{
    return binpow(x, mod - 2);
}*/

/*int divide(int x, int y)
{
    return mul(x, inv(y));
}*/


/*int  fact[200005];

void precalc()
{
    fact[0] = 1;
    for(int i = 1; i < 200005; i++)
    {
        fact[i] = mul(fact[i - 1], i);
    }
      //fact[i]=fact[i-1]*i;
}*/

int pf(int a)
{
	int count = 0;
	while (a % 2 == 0)
	{
		a /= 2;
		count++;
	}
	for (int i = 3; i <= sqrt(a); i += 2)
	{
		while (a % i == 0)
		{
			a /= i;
			count++;
		}
	}
	if (a != 1)
	{
		return count + 1;
	}
	return count;
}

signed main()
{
	int t, a, b, k;
	//calc();
	cin >> t;
	while (t--)
	{
		cin >> a >> b >> k;
		if ((a == b && k == 1) || (a == 1 && b == 1))
		{
			cout << "NO" << endl;
			continue;
		}
		else if (k == 1)
		{
			if (a % b == 0 || b % a == 0)
			{
				cout << "YES" << endl;
			}
			else
			{
				cout << "NO" << endl;
			}
		}
		else
		{	int x = pf(a); int y = pf(b);
			//cout << x << " " << y << endl;
			if (x + y >= k)
			{
				cout << "YES" << endl;
			}
			else
			{
				cout << "NO" << endl;
			}
		}
	}
}
```