// Created by Pratik
// NIT PATNA

#include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
// using namespace __gnu_pbds;

using namespace std;
#define M                    1000000007
#define pi                   3.14159265358979323846
#define ll                   long long
#define lld                  long double

// Pair
#define pii                  pair<int, int>
#define pll                  pair<ll, ll>

// Vector
#define vl                   vector<ll >
#define vi                   vector<int>
#define vpi                  vector<pii>
#define vpl                  vector<pll>
#define pb                   push_back
#define mp                   make_pair


// Search
#define lb                   lower_bound
#define ub                   upper_bound
#define mina                 *min_element
#define mama                 *max_element
#define bsrch                binary_search

////////
#define F                    first
#define S                    second
#define cel(x,a)             ((x + a - 1) / a)
#define all(v)               v.begin(), v.end()
#define allrev(v)            v.rbegin(), v.rend()
#define lcm(m, n)            ((m / __gcd(m, n))*n)
#define deb(...)             cerr << "(" << #__VA_ARGS__ << "):", dbg(__VA_ARGS__)
#define ms(arr, v)           memset(arr, v, sizeof(arr))
#define ps(x,y)              fixed << setprecision(y) << x
#define _X_                  ios_base::sync_with_stdio(false); cin.tie(NULL)

//pbds
#define ordered                 tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

// Input / Output
#define scn(str)             scanf("%s", str)
#define pri(str)             printf("%s\n", str)


const int N = 2.5e6 + 4;

inline void  dbg()           { cerr << endl; }


template <typename T, typename... V>
inline void  dbg(T t, V... v) {cerr << ' ' << t; dbg(v...);}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


void solve()
{
    int a,b,k;
    cin >> a >> b >> k;
    if(k>=130)
    {
		cout << "NO\n";
		return;
	}
	int mn = 2;
	if((a%b==0 || b%a==0) && a!=b)mn--;
	int aa = a,bb = b;
	int p1 = 0;
	int tmp = 0;
	while(a%2==0)
	{
		a /= 2;
		tmp++;
	}
	p1 += tmp;
	for(int i = 3; i*i<=aa; i+=2)
	{
		if(a%i==0)
		{
			int cnt = 0;
			while(a%i==0)
			{
				a /= i;
				cnt++;
			}
			p1 += cnt;
		}
	}
	if(a>1)p1++;
	int p2 = 0;
	tmp = 0;
	while(b%2==0)
	{
		b /= 2;
		tmp++;
	}
	p2 += tmp;
	for(int i = 3; i*i<=bb; i+=2)
	{
		if(b%i==0)
		{
			int cnt = 0;
			while(b%i==0)
			{
				b /= i;
				cnt++;
			}
			p2 += cnt;
		}
	}
	if(b>1)p2++;
	//deb(p1,p2);
	int mx = p1+p2;
	if(k>=mn && k<=mx)cout << "YES\n";
	else cout << "NO\n";
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    // clock_t time_req = clock();

    int t = 1;
     cin>> t;
    while (t--) {
       solve();



   }


    // time_req = clock() - time_req;
    // cout << (float)time_req / CLOCKS_PER_SEC;
   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
// Created by Pratik
// NIT PATNA

#include <bits/stdc++.h>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
// using namespace __gnu_pbds;

using namespace std;
#define M                    1000000007
#define pi                   3.14159265358979323846
#define ll                   long long
#define lld                  long double

// Pair
#define pii                  pair<int, int>
#define pll                  pair<ll, ll>

// Vector
#define vl                   vector<ll >
#define vi                   vector<int>
#define vpi                  vector<pii>
#define vpl                  vector<pll>
#define pb                   push_back
#define mp                   make_pair


// Search
#define lb                   lower_bound
#define ub                   upper_bound
#define mina                 *min_element
#define mama                 *max_element
#define bsrch                binary_search

////////
#define F                    first
#define S                    second
#define cel(x,a)             ((x + a - 1) / a)
#define all(v)               v.begin(), v.end()
#define allrev(v)            v.rbegin(), v.rend()
#define lcm(m, n)            ((m / __gcd(m, n))*n)
#define deb(...)             cerr << "(" << #__VA_ARGS__ << "):", dbg(__VA_ARGS__)
#define ms(arr, v)           memset(arr, v, sizeof(arr))
#define ps(x,y)              fixed << setprecision(y) << x
#define _X_                  ios_base::sync_with_stdio(false); cin.tie(NULL)

//pbds
#define ordered                 tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

// Input / Output
#define scn(str)             scanf("%s", str)
#define pri(str)             printf("%s\n", str)


const int N = 2.5e6 + 4;

inline void  dbg()           { cerr << endl; }


template <typename T, typename... V>
inline void  dbg(T t, V... v) {cerr << ' ' << t; dbg(v...);}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


void solve()
{
    int a,b,k;
    cin >> a >> b >> k;
    if(k>=130)
    {
		cout << "NO\n";
		return;
	}
	int mn = 2;
	if((a%b==0 || b%a==0) && a!=b)mn--;
	int aa = a,bb = b;
	int p1 = 0;
	int tmp = 0;
	while(a%2==0)
	{
		a /= 2;
		tmp++;
	}
	p1 += tmp;
	for(int i = 3; i*i<=aa; i+=2)
	{
		if(a%i==0)
		{
			int cnt = 0;
			while(a%i==0)
			{
				a /= i;
				cnt++;
			}
			p1 += cnt;
		}
	}
	if(a>1)p1++;
	int p2 = 0;
	tmp = 0;
	while(b%2==0)
	{
		b /= 2;
		tmp++;
	}
	p2 += tmp;
	for(int i = 3; i*i<=bb; i+=2)
	{
		if(b%i==0)
		{
			int cnt = 0;
			while(b%i==0)
			{
				b /= i;
				cnt++;
			}
			p2 += cnt;
		}
	}
	if(b>1)p2++;
	//deb(p1,p2);
	int mx = p1+p2;
	if(k>=mn && k<=mx)cout << "YES\n";
	else cout << "NO\n";
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    // clock_t time_req = clock();

    int t = 1;
     cin>> t;
    while (t--) {
       solve();



   }


    // time_req = clock() - time_req;
    // cout << (float)time_req / CLOCKS_PER_SEC;
   return 0;
}

```