/*
    This code belongs to Aadit Ambadkar
    Date: 2021-06-11 09:41:08
*/
#include <bits/stdc++.h>
using namespace::std;

typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define FMOD 998244353
#define MOD 1000000007

int fac(int n) {
    ll ans = 0;
    while (n%2==0) {
        n/=2;
        ans++;
    }
    for (int i = 3; i <= sqrt(n); i+=2) {
        while (n%i==0) {
            n/=i;
            ans++;
        }
    }
    if (n>1) ans++;
    return ans;
}

void solve() {
    int a, b, k; cin >> a >> b >> k;
    if (k==1) {
        if (a==b) {
            cout << "NO\n";
        }
        else if (a%b==0 || b%a==0) {
            cout << "YES\n";
        } else cout << "NO\n";
        return;
    }
    if (fac(a)+fac(b)>=k) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
    fastio;
    int t; cin >> t; while (t--) solve();
}
### 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
/*
    This code belongs to Aadit Ambadkar
    Date: 2021-06-11 09:41:08
*/
#include <bits/stdc++.h>
using namespace::std;

typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define FMOD 998244353
#define MOD 1000000007

int fac(int n) {
    ll ans = 0;
    while (n%2==0) {
        n/=2;
        ans++;
    }
    for (int i = 3; i <= sqrt(n); i+=2) {
        while (n%i==0) {
            n/=i;
            ans++;
        }
    }
    if (n>1) ans++;
    return ans;
}

void solve() {
    int a, b, k; cin >> a >> b >> k;
    if (k==1) {
        if (a==b) {
            cout << "NO\n";
        }
        else if (a%b==0 || b%a==0) {
            cout << "YES\n";
        } else cout << "NO\n";
        return;
    }
    if (fac(a)+fac(b)>=k) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
    fastio;
    int t; cin >> t; while (t--) solve();
}
```