#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a) for (int i=0; i<(a); i++)
#define FORI(i, a, b) for (int i=a; i<(b); i++)
#define FORd(i, a) for (int i=(a)-1; i>=0; i--)
#define FORId(i, a, b) for (int i=(a)-1; i>=(b); i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define printav(i, x) FOR(i, x.size()) cout << x[i] << " "; cout << "\n";
 
#define sz(x) (int) (x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

const int INF = 0x3f3f3f3f;

#define MAX 150
int dp[MAX];

ll pf(ll n)
{
    ll count = 0;

    for (int d : {2, 3, 5})
    {
        while (n % d == 0)
        {
            count++;
            n /= d;
        }
    }

    static array<int, 8> increments = {4, 2, 4, 2, 4, 6, 2, 6};
    int i = 0;
    for (ll d = 7; d * d <= n; d += increments[i++])
    {
        while (n % d == 0)
        {
            count++;
            n /= d;
        }

        if (i == 8)
            i = 0;
    }

    if (n > 1)
        count++;

    return count;
}

void solve()
{
    ll a,b,k;
    cin >> a >> b >> k;

    if (k == 1)
    {
        if (a!=b and (a%b == 0 or b%a == 0))
            cout << "Yes\n";
        else
            cout << "No\n";

        return;
    }

    ll ans = pf(a)+pf(b);

    if (k <= ans)
        cout << "Yes\n";
    else
        cout << "No\n";
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    memset(dp, -1, sizeof(dp));
    
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
### Prompt

Your task is to create 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>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a) for (int i=0; i<(a); i++)
#define FORI(i, a, b) for (int i=a; i<(b); i++)
#define FORd(i, a) for (int i=(a)-1; i>=0; i--)
#define FORId(i, a, b) for (int i=(a)-1; i>=(b); i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define printav(i, x) FOR(i, x.size()) cout << x[i] << " "; cout << "\n";
 
#define sz(x) (int) (x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

const int INF = 0x3f3f3f3f;

#define MAX 150
int dp[MAX];

ll pf(ll n)
{
    ll count = 0;

    for (int d : {2, 3, 5})
    {
        while (n % d == 0)
        {
            count++;
            n /= d;
        }
    }

    static array<int, 8> increments = {4, 2, 4, 2, 4, 6, 2, 6};
    int i = 0;
    for (ll d = 7; d * d <= n; d += increments[i++])
    {
        while (n % d == 0)
        {
            count++;
            n /= d;
        }

        if (i == 8)
            i = 0;
    }

    if (n > 1)
        count++;

    return count;
}

void solve()
{
    ll a,b,k;
    cin >> a >> b >> k;

    if (k == 1)
    {
        if (a!=b and (a%b == 0 or b%a == 0))
            cout << "Yes\n";
        else
            cout << "No\n";

        return;
    }

    ll ans = pf(a)+pf(b);

    if (k <= ans)
        cout << "Yes\n";
    else
        cout << "No\n";
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    memset(dp, -1, sizeof(dp));
    
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
```