#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<climits>
#include<set>
#include<map>
#include<cmath>
#include<iomanip>
#include<iterator>
#include<queue>
#include<stack>
#include<cctype>
#include<deque>
#include<time.h>
#include<bitset>
#include<random>
#include<functional>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<numeric>
#include<chrono>
#include<sstream>
#include<valarray> 
#include<list>
#include<complex>
#include<cassert>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define vvll vector<vector<ll>>
#define vvi vector<vector<int>>
#define vpii vector<pair<int, int>>
#define vll vector<ll>
#define vld vector<ld>
#define pii pair<int,int>
#define pll pair<long long,long long>
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define pb push_back
#define forab(i, a, b) for (long long i = a; i < b; i++)
#define for0(i, n) for(int  i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define en '\n'

const ld EPS = 0.000001;

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for (auto& i : a)
        cin >> i;
    return in;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T>& a) {
    for (auto& i : a)
        cout << i << ' ';
    return out;
}
const int maxn = 1e6 + 11;
const int INF = 1e9 + 11;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else return gcd(b, a % b);
}

int a, b, c, k;

int fct(int x) {
    int rz = 0;
    for (int i = 2; i * i <= x; i++) {
        while (x % i == 0) {
            rz++;
            x /= i;
        }
    }
    if (x != 1)
        rz++;
    return rz;
}

void solve() {
    cin >> a >> b >> k;
    
    int n = fct(a) + fct(b);

    int m;
    if (a == b)
        m = 0;
    else if (a % b == 0 || b % a == 0)
        m = 1;
    else
        m = 2;
    if (k <= n && k>=m && k!=1|| k==1 && m==1) {
        cout << "YES\n";
    }
    else
        cout << "NO\n";
}


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

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

### Prompt

Please create a solution in cpp 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<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<climits>
#include<set>
#include<map>
#include<cmath>
#include<iomanip>
#include<iterator>
#include<queue>
#include<stack>
#include<cctype>
#include<deque>
#include<time.h>
#include<bitset>
#include<random>
#include<functional>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<numeric>
#include<chrono>
#include<sstream>
#include<valarray> 
#include<list>
#include<complex>
#include<cassert>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define vvll vector<vector<ll>>
#define vvi vector<vector<int>>
#define vpii vector<pair<int, int>>
#define vll vector<ll>
#define vld vector<ld>
#define pii pair<int,int>
#define pll pair<long long,long long>
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define pb push_back
#define forab(i, a, b) for (long long i = a; i < b; i++)
#define for0(i, n) for(int  i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define en '\n'

const ld EPS = 0.000001;

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for (auto& i : a)
        cin >> i;
    return in;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T>& a) {
    for (auto& i : a)
        cout << i << ' ';
    return out;
}
const int maxn = 1e6 + 11;
const int INF = 1e9 + 11;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else return gcd(b, a % b);
}

int a, b, c, k;

int fct(int x) {
    int rz = 0;
    for (int i = 2; i * i <= x; i++) {
        while (x % i == 0) {
            rz++;
            x /= i;
        }
    }
    if (x != 1)
        rz++;
    return rz;
}

void solve() {
    cin >> a >> b >> k;
    
    int n = fct(a) + fct(b);

    int m;
    if (a == b)
        m = 0;
    else if (a % b == 0 || b % a == 0)
        m = 1;
    else
        m = 2;
    if (k <= n && k>=m && k!=1|| k==1 && m==1) {
        cout << "YES\n";
    }
    else
        cout << "NO\n";
}


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

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

```