///              B I S M I L L A H I R  R A H M A N I R  R A H I M

#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef bool                      boo;
typedef int                       li;
typedef long long int             ll;
typedef unsigned long long int    l1;
typedef double                    db;
//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

typedef vector < li >                   vli;
typedef vector < ll >                   vll;
typedef set < li >                      sli;
typedef set < ll >                      sll;
typedef pair < li , li >                pli;
typedef pair < ll , ll >                pll;
typedef map < li ,li >                  mli;
typedef map < ll ,ll >                  mll;
typedef vector < pair < li , li > >     vpi;
typedef vector < pair < ll , ll > >     vpl;

//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#define tc                        int t;cin>>t;while(t--)
#define inp_i(a,n)                for(i=0; i<n ;i++) cin>>a[i]
#define lp(i,a,b)                 for(i=a;i<b;i++)
#define len(z)                    z.begin(),z.end()
#define faster                    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define input_txt                 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define nl                        <<"\n"
#define spc                       <<" "
#define sp                        <<" "<<
#define co(x)                     cout<<x nl
#define sz(a)                     a.size()
#define cy                        cout<<"YES" nl
#define cn                        cout<<"NO" nl
#define pb                        push_back
#define F                         first
#define S                         second
#define pi                        2*acos(0.0)
#define clr(z)                    z.clear()
#define rn                        return
#define gcd(a,b)                  __gcd(a,b)
#define mem(b,z)                  memset(b,z,sizeof(b))
#define fixed(x)                  fixed<<setprecision(x)
const int lx=3e5+123;
const ll mod = 1e9 + 7;

void solve()
{
    li a, b, k, a1, b1, a2=0, b2=0, i;
    cin>>a>>b>>k;
    if(a>b) swap(a, b);
    if(k==1)
    {
        if(a<b && b%a==0) cy;
        else cn;
        rn;
    }
    a1=a; b1=b;
    for(i=2; i*i <= a1; i++)
    {
        if(i>a1) break;
        if(a1%i) continue;
        while(a1%i==0)
        {
            a1/=i;
            a2++;
        }
    }
    if(a1>1) a2++;

    for(i=2; i*i <= b1; i++)
    {
        if(i>b1) break;
        if(b1%i) continue;
        while(b1%i==0)
        {
            b1/=i;
            b2++;
         //   co(b1 sp b2);
        }
    }
    if(b1>1) b2++;
    //co(a2 sp b2);
    if(a2+b2<k) cn;
    else cy;
}

void init_code()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
}

int main()
{
faster
tc
//init_code();
solve();
// A L H A M D U L I L L A H
// 1 2 3 2 1

}

/*
ll gcd(ll a, ll b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

void number_of_divisors(li n)
{
    //Number of divisors of every number between 1 to n
    for(li i = 1; i*i <= n; i++)
    {
        for(li j = i*i; j <= n; j += i)
        {
            if(i*i == j)
                a[j]++;
            else
                a[j] += 2;
        }
    }
}

void sum_of_divisor()
{
    for(li i = 1; i * i <= 1e7; i++)
    {
        for(li j = i*i; j < 1e7; j += i)
        {
            if(j == i*i)
                a[j] += i;
            else
                a[j] += i+(j/i);
        }
    }
}

void subsequence_find_TMT()
{
     for(i = 0; i < n; i++)
    {
        if(s[i]=='T') a++;
        else a--;

        if(a<0 or a>n/3)
        {
            cn;
            rn;
        }
    }
    if(a==n/3) cy;
    else cn;
}

*/


### 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
///              B I S M I L L A H I R  R A H M A N I R  R A H I M

#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef bool                      boo;
typedef int                       li;
typedef long long int             ll;
typedef unsigned long long int    l1;
typedef double                    db;
//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

typedef vector < li >                   vli;
typedef vector < ll >                   vll;
typedef set < li >                      sli;
typedef set < ll >                      sll;
typedef pair < li , li >                pli;
typedef pair < ll , ll >                pll;
typedef map < li ,li >                  mli;
typedef map < ll ,ll >                  mll;
typedef vector < pair < li , li > >     vpi;
typedef vector < pair < ll , ll > >     vpl;

//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#define tc                        int t;cin>>t;while(t--)
#define inp_i(a,n)                for(i=0; i<n ;i++) cin>>a[i]
#define lp(i,a,b)                 for(i=a;i<b;i++)
#define len(z)                    z.begin(),z.end()
#define faster                    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define input_txt                 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define nl                        <<"\n"
#define spc                       <<" "
#define sp                        <<" "<<
#define co(x)                     cout<<x nl
#define sz(a)                     a.size()
#define cy                        cout<<"YES" nl
#define cn                        cout<<"NO" nl
#define pb                        push_back
#define F                         first
#define S                         second
#define pi                        2*acos(0.0)
#define clr(z)                    z.clear()
#define rn                        return
#define gcd(a,b)                  __gcd(a,b)
#define mem(b,z)                  memset(b,z,sizeof(b))
#define fixed(x)                  fixed<<setprecision(x)
const int lx=3e5+123;
const ll mod = 1e9 + 7;

void solve()
{
    li a, b, k, a1, b1, a2=0, b2=0, i;
    cin>>a>>b>>k;
    if(a>b) swap(a, b);
    if(k==1)
    {
        if(a<b && b%a==0) cy;
        else cn;
        rn;
    }
    a1=a; b1=b;
    for(i=2; i*i <= a1; i++)
    {
        if(i>a1) break;
        if(a1%i) continue;
        while(a1%i==0)
        {
            a1/=i;
            a2++;
        }
    }
    if(a1>1) a2++;

    for(i=2; i*i <= b1; i++)
    {
        if(i>b1) break;
        if(b1%i) continue;
        while(b1%i==0)
        {
            b1/=i;
            b2++;
         //   co(b1 sp b2);
        }
    }
    if(b1>1) b2++;
    //co(a2 sp b2);
    if(a2+b2<k) cn;
    else cy;
}

void init_code()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
}

int main()
{
faster
tc
//init_code();
solve();
// A L H A M D U L I L L A H
// 1 2 3 2 1

}

/*
ll gcd(ll a, ll b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

void number_of_divisors(li n)
{
    //Number of divisors of every number between 1 to n
    for(li i = 1; i*i <= n; i++)
    {
        for(li j = i*i; j <= n; j += i)
        {
            if(i*i == j)
                a[j]++;
            else
                a[j] += 2;
        }
    }
}

void sum_of_divisor()
{
    for(li i = 1; i * i <= 1e7; i++)
    {
        for(li j = i*i; j < 1e7; j += i)
        {
            if(j == i*i)
                a[j] += i;
            else
                a[j] += i+(j/i);
        }
    }
}

void subsequence_find_TMT()
{
     for(i = 0; i < n; i++)
    {
        if(s[i]=='T') a++;
        else a--;

        if(a<0 or a>n/3)
        {
            cn;
            rn;
        }
    }
    if(a==n/3) cy;
    else cn;
}

*/


```