#include <bits/stdc++.h>
#define FastIO                   \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define PI acos(-1)
#define Mod 1000000007
#define endl      "\n"

using namespace std;
int cs = 1;

void file();
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int dx[] = { +0, +0, -1, +1};
int dy[] = { +1, -1, +0, +0};

int X[] = { +0, +0, +1, -1, -1, +1, -1, +1}; // Kings Move
int Y[] = { -1, +1, +0, +0, +1, +1, -1, -1}; // Kings Move

int kx[] = { -2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
int ky[] = { -1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
bool valid(int r, int c, int n, int m)
{
    return (r >= 0 && r < n && c >= 0 && c < m);
}

//-------------------------------------------------------------------

//  priority_queue<int,vector<int>,greater<int>>pq;
/// some useful functions

template <class T> inline T bigMod(T p, T e, T M) {T ret = 1; for (; e > 0; e >>= 1) { if (e & 1) ret = (ret * p) % M; p = (p * p) % M;} return (T)ret;}
template <class T> inline T modInverse(T a, T M) {return bigMod(a, M - 2, M);}
template <class T> inline T gcd(T a, T b) {if (b == 0)return a; return gcd(b, a % b);}
template <class T> inline T lcm(T a, T b) {a = abs(a); b = abs(b); return (a / gcd(a, b)) * b;}

/// some useful functions

vector <ll> findPrimeFactors(ll n)
{
    vector<ll> primeFactors;
    while (n % 2 == 0) primeFactors.push_back(2), n = n / 2;
    for (ll i = 3; i * i <= n; i = i + 2)
    {
        while (n % i == 0)
        {
            primeFactors.push_back(i);
            n = n / i;
        }
    }
    if (n > 2) primeFactors.push_back(n);
    return primeFactors;
}

vector<long long> allDivisiors(long long n)
{
    vector<long long>divisors;
    ll limit = sqrt(n + 1);
    for (ll i = 1; i <= limit; i++)
    {
        if (n % i == 0)
        {
            if (n / i == i) divisors.push_back(i);
            else divisors.push_back(i), divisors.push_back(n / i);
        }
    }
    return divisors;
}

bool isPrime(ll n)
{
    if (n == 2 or n == 3) return true;
    if (n % 2 == 0) return false;
    for (ll i = 3; i * i <= n; i += 2) if (n % i == 0) return false;
    return true;
}

ll power(ll n, ll p)
{
    if (p == 0) return 1;
    if (p == 1) return n;
    ll ans = 1;
    while (p)
    {
        if (p & 1) ans = ans * n;
        n = n * n;
        p = p / 2;
    }
    return ans;
}

bool isPalindrome(string s)
{
    int N = s.size();
    for ( int i = 0; i < N / 2; i++)
    {
        if (s[i] != s[N - 1 - i]) return 0;
    }
    return 1;
}

//-------------------------------------------------------------------
const int inf = 2000000000;
const ll infLL = 9000000000000000000;

const int lim = 25000;

//-------------------------------------------------------------------

bool ckr[100005];
vector<ll>primes;
void seave()
{

    for ( int i = 3; i * i <= 100000; i += 2)
    {
        for ( int j = i * i; j <= 100000; j += (i + i))
        {
            ckr[j] = true;
        }
    }
    primes.push_back(2);

    for ( int i = 3; i <= 100000; i += 2)
    {
        if (!ckr[i])primes.push_back(i);
    }
}

void solve()
{
    ll a, b, n;
    cin >> a >> b >> n;
    if (a > b) swap(a, b);

    ll p = 0, q = 0, aa = a, bb = b;

    for ( int i = 0; primes[i]*primes[i] <= aa; i++)
    {
        if (aa % primes[i] == 0)
        {
            while (aa % primes[i] == 0)aa /= primes[i], p++;
        }
    }
    if (aa > 1)p++;

    for ( int i = 0; primes[i]*primes[i] <= bb; i++)
    {
        if (bb % primes[i] == 0)
        {
            while (bb % primes[i] == 0)bb /= primes[i], q++;
        }
    }
    if (bb > 1)q++;

    if (n == 1)
    {
        if (b % a == 0 && a != b) cout << "YES\n";
        else cout << "NO\n";
    }
    else
    {
        if (n <= (p + q)) cout << "YES\n";
        else cout << "NO\n";
    }
}
int main()
{

    seave();
    FastIO;
    file();
    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

void file()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

### Prompt

In CPP, your task is to solve 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 FastIO                   \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define PI acos(-1)
#define Mod 1000000007
#define endl      "\n"

using namespace std;
int cs = 1;

void file();
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int dx[] = { +0, +0, -1, +1};
int dy[] = { +1, -1, +0, +0};

int X[] = { +0, +0, +1, -1, -1, +1, -1, +1}; // Kings Move
int Y[] = { -1, +1, +0, +0, +1, +1, -1, -1}; // Kings Move

int kx[] = { -2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
int ky[] = { -1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
bool valid(int r, int c, int n, int m)
{
    return (r >= 0 && r < n && c >= 0 && c < m);
}

//-------------------------------------------------------------------

//  priority_queue<int,vector<int>,greater<int>>pq;
/// some useful functions

template <class T> inline T bigMod(T p, T e, T M) {T ret = 1; for (; e > 0; e >>= 1) { if (e & 1) ret = (ret * p) % M; p = (p * p) % M;} return (T)ret;}
template <class T> inline T modInverse(T a, T M) {return bigMod(a, M - 2, M);}
template <class T> inline T gcd(T a, T b) {if (b == 0)return a; return gcd(b, a % b);}
template <class T> inline T lcm(T a, T b) {a = abs(a); b = abs(b); return (a / gcd(a, b)) * b;}

/// some useful functions

vector <ll> findPrimeFactors(ll n)
{
    vector<ll> primeFactors;
    while (n % 2 == 0) primeFactors.push_back(2), n = n / 2;
    for (ll i = 3; i * i <= n; i = i + 2)
    {
        while (n % i == 0)
        {
            primeFactors.push_back(i);
            n = n / i;
        }
    }
    if (n > 2) primeFactors.push_back(n);
    return primeFactors;
}

vector<long long> allDivisiors(long long n)
{
    vector<long long>divisors;
    ll limit = sqrt(n + 1);
    for (ll i = 1; i <= limit; i++)
    {
        if (n % i == 0)
        {
            if (n / i == i) divisors.push_back(i);
            else divisors.push_back(i), divisors.push_back(n / i);
        }
    }
    return divisors;
}

bool isPrime(ll n)
{
    if (n == 2 or n == 3) return true;
    if (n % 2 == 0) return false;
    for (ll i = 3; i * i <= n; i += 2) if (n % i == 0) return false;
    return true;
}

ll power(ll n, ll p)
{
    if (p == 0) return 1;
    if (p == 1) return n;
    ll ans = 1;
    while (p)
    {
        if (p & 1) ans = ans * n;
        n = n * n;
        p = p / 2;
    }
    return ans;
}

bool isPalindrome(string s)
{
    int N = s.size();
    for ( int i = 0; i < N / 2; i++)
    {
        if (s[i] != s[N - 1 - i]) return 0;
    }
    return 1;
}

//-------------------------------------------------------------------
const int inf = 2000000000;
const ll infLL = 9000000000000000000;

const int lim = 25000;

//-------------------------------------------------------------------

bool ckr[100005];
vector<ll>primes;
void seave()
{

    for ( int i = 3; i * i <= 100000; i += 2)
    {
        for ( int j = i * i; j <= 100000; j += (i + i))
        {
            ckr[j] = true;
        }
    }
    primes.push_back(2);

    for ( int i = 3; i <= 100000; i += 2)
    {
        if (!ckr[i])primes.push_back(i);
    }
}

void solve()
{
    ll a, b, n;
    cin >> a >> b >> n;
    if (a > b) swap(a, b);

    ll p = 0, q = 0, aa = a, bb = b;

    for ( int i = 0; primes[i]*primes[i] <= aa; i++)
    {
        if (aa % primes[i] == 0)
        {
            while (aa % primes[i] == 0)aa /= primes[i], p++;
        }
    }
    if (aa > 1)p++;

    for ( int i = 0; primes[i]*primes[i] <= bb; i++)
    {
        if (bb % primes[i] == 0)
        {
            while (bb % primes[i] == 0)bb /= primes[i], q++;
        }
    }
    if (bb > 1)q++;

    if (n == 1)
    {
        if (b % a == 0 && a != b) cout << "YES\n";
        else cout << "NO\n";
    }
    else
    {
        if (n <= (p + q)) cout << "YES\n";
        else cout << "NO\n";
    }
}
int main()
{

    seave();
    FastIO;
    file();
    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

void file()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

```