#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); (int)i < (b); i++)
#define REP(i, a) for (int i = 0; i < (int)(a); i++)
#define ALL(i) i.begin(), i.end()
#define rALL(i) i.rbegin(), i.rend()
#define PB push_back

typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<string> VS;
template <class T>
string i2a(T x)
{
   ostringstream oss;
   oss << x;
   return oss.str();
}

int factor(int n) {
   int d = 2, ans = 0;
   while(d *d <= n) {
      while (n % d == 0) {
         ans += 1;
         n /= d;
      }
      d += 1;
   }
   if (n > 1) ans += 1;
   return ans;
}

int main()
{
#ifdef LOCAL_AJJI
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
#endif
   int t; cin >> t;
   REP(cases, t) {
      int a, b, k;
      cin >> a >> b >> k;
      if (k == 1) {
         if (a == b) {
            cout<<"NO"<<endl; continue;
         }
         if (a% b == 0 or b % a == 0)
            cout << "YES" << endl;
         else
            cout << "NO" << endl;
         continue;
      }

      if ((a == 1) ^ (b == 1)) {
         int d = factor(max(a, b));
         if(k > d) {
            cout << "NO" << endl;

         } else {
            cout << "YES" << endl;
         }
         continue;
      }

      int diva = factor(a), divb = factor(b);
      if(k > diva+divb) {
         cout<<"NO"<<endl;
         continue;
      }

      cout<<"YES"<<endl;


   }

   return 0;
}
### Prompt

Generate a Cpp solution 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 FOR(i, a, b) for (int i = (a); (int)i < (b); i++)
#define REP(i, a) for (int i = 0; i < (int)(a); i++)
#define ALL(i) i.begin(), i.end()
#define rALL(i) i.rbegin(), i.rend()
#define PB push_back

typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<string> VS;
template <class T>
string i2a(T x)
{
   ostringstream oss;
   oss << x;
   return oss.str();
}

int factor(int n) {
   int d = 2, ans = 0;
   while(d *d <= n) {
      while (n % d == 0) {
         ans += 1;
         n /= d;
      }
      d += 1;
   }
   if (n > 1) ans += 1;
   return ans;
}

int main()
{
#ifdef LOCAL_AJJI
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
#endif
   int t; cin >> t;
   REP(cases, t) {
      int a, b, k;
      cin >> a >> b >> k;
      if (k == 1) {
         if (a == b) {
            cout<<"NO"<<endl; continue;
         }
         if (a% b == 0 or b % a == 0)
            cout << "YES" << endl;
         else
            cout << "NO" << endl;
         continue;
      }

      if ((a == 1) ^ (b == 1)) {
         int d = factor(max(a, b));
         if(k > d) {
            cout << "NO" << endl;

         } else {
            cout << "YES" << endl;
         }
         continue;
      }

      int diva = factor(a), divb = factor(b);
      if(k > diva+divb) {
         cout<<"NO"<<endl;
         continue;
      }

      cout<<"YES"<<endl;


   }

   return 0;
}
```