#include <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i, n) for (i = 0; i < n; i++)
#define Fo(i, k, n) for (i = k; k < n ? i < n : i > n; k < n ? i += 1 : i -= 1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
const int maxn = 1e5;

int pn(int x)
{
    int ans = 0;
    for (int i = 2; i * i <= x; i++)
        while (x % i == 0)
        {
            ans++;
            x /= i;
            if (x == 1)
                break;
        }
    if (x > 1)
        ans++;
    return ans;
}
void solve()
{
    ll n, m, k;
    cin >> n >> m >> k;
    ll min_ans = 2;
    ll max_ans = pn(n) + pn(m);
    if (k == 1)
        if (n % m == 0 || m % n == 0)
        {
            if (m == n)
            {
                cout << "NO\n";
                return;
            }
        }
        else
        {
            cout << "NO\n";
            return;
        }
    if (k <= max_ans)
    {
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    cin >> t;
    ll n, x;
    while (t--)
    {
        solve();
    }

    return 0;
}
### 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 <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i, n) for (i = 0; i < n; i++)
#define Fo(i, k, n) for (i = k; k < n ? i < n : i > n; k < n ? i += 1 : i -= 1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
const int maxn = 1e5;

int pn(int x)
{
    int ans = 0;
    for (int i = 2; i * i <= x; i++)
        while (x % i == 0)
        {
            ans++;
            x /= i;
            if (x == 1)
                break;
        }
    if (x > 1)
        ans++;
    return ans;
}
void solve()
{
    ll n, m, k;
    cin >> n >> m >> k;
    ll min_ans = 2;
    ll max_ans = pn(n) + pn(m);
    if (k == 1)
        if (n % m == 0 || m % n == 0)
        {
            if (m == n)
            {
                cout << "NO\n";
                return;
            }
        }
        else
        {
            cout << "NO\n";
            return;
        }
    if (k <= max_ans)
    {
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    cin >> t;
    ll n, x;
    while (t--)
    {
        solve();
    }

    return 0;
}
```