#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

template<class T>
using vec = vector<T>;
template<class T>
using v2d = vector<vector<T>>;

using ld = long double;
using ll = long long;

vec<int> p;

int countfac(int x)
{
    int r = 0;
    for(int i = 0; i < (int) p.size() && p[i] * p[i] <= x; ++i)
    {
        while(x % p[i] == 0)
        {
            r++;
            x /= p[i];
        }
    }
    if (x > 1)
    {
        r++;
    }
    return r;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    vec<int> isp(40000, 1);
    for(int i = 2; i < 40000; i++)
    {
        if (isp[i])
        {
            p.push_back(i);
            for(int j = i*i; j < 40000; j += i)
            {
                isp[i] = 0;
            }
        }
    }
    
    int t;
    cin>>t;
    while(t--)
    {
        int a, b, k;
        cin>>a>>b>>k;
        if (k == 1)
        {
            if ((a % b == 0 || b % a == 0) && a != b)
            {
                cout<<"YES";
            }
            else
            {
                cout<<"NO";
            }
        }
        else
        {
            if (k >= 2 && k <= countfac(a) + countfac(b))
            {
                cout<<"YES";
            }
            else
            {
                cout<<"NO";
            }
        }
        cout<<'\n';
    }
    return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

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
#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

template<class T>
using vec = vector<T>;
template<class T>
using v2d = vector<vector<T>>;

using ld = long double;
using ll = long long;

vec<int> p;

int countfac(int x)
{
    int r = 0;
    for(int i = 0; i < (int) p.size() && p[i] * p[i] <= x; ++i)
    {
        while(x % p[i] == 0)
        {
            r++;
            x /= p[i];
        }
    }
    if (x > 1)
    {
        r++;
    }
    return r;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    vec<int> isp(40000, 1);
    for(int i = 2; i < 40000; i++)
    {
        if (isp[i])
        {
            p.push_back(i);
            for(int j = i*i; j < 40000; j += i)
            {
                isp[i] = 0;
            }
        }
    }
    
    int t;
    cin>>t;
    while(t--)
    {
        int a, b, k;
        cin>>a>>b>>k;
        if (k == 1)
        {
            if ((a % b == 0 || b % a == 0) && a != b)
            {
                cout<<"YES";
            }
            else
            {
                cout<<"NO";
            }
        }
        else
        {
            if (k >= 2 && k <= countfac(a) + countfac(b))
            {
                cout<<"YES";
            }
            else
            {
                cout<<"NO";
            }
        }
        cout<<'\n';
    }
    return 0;
}
```