                                                 /*Bismillahir Rahmanir Rahim*/
     
    #pragma GCC optimize ("Ofast")
    #include<bits/stdc++.h>
    #define _GLIBCXX_DEBUG
    #define ff      first
    #define ss      second
    #define ll      long long int
    #define dd      double
    #define pb      push_back
    #define pr      pair<ll,ll>
    #define pqmx    priority_queue<ll>
    #define pqmn    priority_queue<ll,vector<ll>,greater<ll>>
    // #define MOD     1000000007
    #define pd(x,y)     fixed<<setprecision(y)<<x
    #define w(x)     ll x; cin>>x; while(x--)
    #define loop(i,x,n) for(ll i=x;i<n;i++)
    #define rloop(x,n) for(ll i=n-1;i>=x;i--)
    #define all(x)            (x).begin(),(x).end()
    #define rall(x)            (x).rbegin(),(x).rend()
    #define dbg1(x)      cout<<"["<<#x<<": "<<x<<"]"<<endl;
    #define dbg2(x, y) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<endl;
    #define dbg3(x, y, z) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]"<<endl;
    #define dbg4(x, y, z, k) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]"<<"  ["<<#k<<": "<<k<<"]"<<endl;
    #define no          cout << "NO" << endl;
    #define yes          cout << "YES" << endl;
    // #define endl            "\n"
    #define FAST      ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
    #define pi        3.141592653
     
    ll const N=100006;
    //Samee Sevas
     
    using namespace std;
    vector<ll> prime;
    ll f[N]={0};
    void inti(){
    vector<bool> is_prime(N+1, true);
     
    for (int i = 2; i <= N; i++) {
        if (is_prime[i] && (long long)i * i <= N) {
            for (int j = i * i; j <= N; j += i)
                is_prime[j] = false;
        }
    }
    loop(i,2,N)
    {
      if(is_prime[i]==true)
      prime.push_back(i);
    }
      
     
    }
    void solve()
    {
      
      ll n,m,r,k;
      cin>>n>>m>>k;
      ll x1=0,x2=0;
      ll x=n,y=m;
      for(ll i=0;i<prime.size();i++)
      {
          if(prime[i]*prime[i]>x) break;
          if(x%prime[i]==0)
          {
              while(x%prime[i]==0)
              {
                  x1++;
                  x/=prime[i];
              }
          }
     
      }
      if(x>1)
      x1++;
      x=m;
        for(ll i=0;i<prime.size();i++)
      {
          if(prime[i]*prime[i]>x) break;
          if(x%prime[i]==0)
          {
              while(x%prime[i]==0)
              {
                  x2++;
                  x/=prime[i];
              }
          }
     
      }
      if(x>1)
      x2++;
      y=min(x1,x2);
      //dbg1(y);
      if(k>=2){
        y=x1+x2;
        if(y<k) 
      no
      else
      yes
      }
      else
      {
          ll mn=min(n,m);
          ll mx=max(n,m);
          if(mx%mn==0)
          {
              ll z=mx/mn;
              if(z>1)
              {
                  //dbg1(1)
                  yes
              }
              else
              no
          }
          else
          no
      }
      
     
     
    }
    signed main()
    {
        FAST;
             ll t=1,u=0; 
             cin>>t; 
           inti();
             while(t--)
             {
                // cout<<"Case "<<++u<<": ";
                 solve();
             }
           
       
     }


### Prompt

Create a solution in cpp for 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
                                                 /*Bismillahir Rahmanir Rahim*/
     
    #pragma GCC optimize ("Ofast")
    #include<bits/stdc++.h>
    #define _GLIBCXX_DEBUG
    #define ff      first
    #define ss      second
    #define ll      long long int
    #define dd      double
    #define pb      push_back
    #define pr      pair<ll,ll>
    #define pqmx    priority_queue<ll>
    #define pqmn    priority_queue<ll,vector<ll>,greater<ll>>
    // #define MOD     1000000007
    #define pd(x,y)     fixed<<setprecision(y)<<x
    #define w(x)     ll x; cin>>x; while(x--)
    #define loop(i,x,n) for(ll i=x;i<n;i++)
    #define rloop(x,n) for(ll i=n-1;i>=x;i--)
    #define all(x)            (x).begin(),(x).end()
    #define rall(x)            (x).rbegin(),(x).rend()
    #define dbg1(x)      cout<<"["<<#x<<": "<<x<<"]"<<endl;
    #define dbg2(x, y) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<endl;
    #define dbg3(x, y, z) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]"<<endl;
    #define dbg4(x, y, z, k) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]"<<"  ["<<#k<<": "<<k<<"]"<<endl;
    #define no          cout << "NO" << endl;
    #define yes          cout << "YES" << endl;
    // #define endl            "\n"
    #define FAST      ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
    #define pi        3.141592653
     
    ll const N=100006;
    //Samee Sevas
     
    using namespace std;
    vector<ll> prime;
    ll f[N]={0};
    void inti(){
    vector<bool> is_prime(N+1, true);
     
    for (int i = 2; i <= N; i++) {
        if (is_prime[i] && (long long)i * i <= N) {
            for (int j = i * i; j <= N; j += i)
                is_prime[j] = false;
        }
    }
    loop(i,2,N)
    {
      if(is_prime[i]==true)
      prime.push_back(i);
    }
      
     
    }
    void solve()
    {
      
      ll n,m,r,k;
      cin>>n>>m>>k;
      ll x1=0,x2=0;
      ll x=n,y=m;
      for(ll i=0;i<prime.size();i++)
      {
          if(prime[i]*prime[i]>x) break;
          if(x%prime[i]==0)
          {
              while(x%prime[i]==0)
              {
                  x1++;
                  x/=prime[i];
              }
          }
     
      }
      if(x>1)
      x1++;
      x=m;
        for(ll i=0;i<prime.size();i++)
      {
          if(prime[i]*prime[i]>x) break;
          if(x%prime[i]==0)
          {
              while(x%prime[i]==0)
              {
                  x2++;
                  x/=prime[i];
              }
          }
     
      }
      if(x>1)
      x2++;
      y=min(x1,x2);
      //dbg1(y);
      if(k>=2){
        y=x1+x2;
        if(y<k) 
      no
      else
      yes
      }
      else
      {
          ll mn=min(n,m);
          ll mx=max(n,m);
          if(mx%mn==0)
          {
              ll z=mx/mn;
              if(z>1)
              {
                  //dbg1(1)
                  yes
              }
              else
              no
          }
          else
          no
      }
      
     
     
    }
    signed main()
    {
        FAST;
             ll t=1,u=0; 
             cin>>t; 
           inti();
             while(t--)
             {
                // cout<<"Case "<<++u<<": ";
                 solve();
             }
           
       
     }


```