#include <bits/stdc++.h>

using namespace std;
vector<long long int>v;
long long int p[1000000];
void s()
{
    memset(p,1,sizeof p);
    p[0]=p[1]=0;
    for(long long int i=0;i<=100000;i++)
    {
        if(p[i])
        for(long long int j=i*i;j<=100000;j+=i)
        {
            p[j]=0;
        }
    }
    for(long long int i=0;i<100000;i++)
        if(p[i])v.push_back(i);
}
int main()
{
    s();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int a,b,k;
        scanf("%lld%lld%lld",&a,&b,&k);
        if(k==1)
        {
            if(a==b)
            {
                printf("NO\n");
                continue;
            }
            if(a%b==0 || b%a==0)
            {
                printf("YES\n");
                continue;
            }
            printf("NO\n");
            continue;
        }
        long long int cnta=0,cntb=0;
        for(auto x:v)
        {
            if(x*x>a)break;
            while( a%x==0)
            {
                cnta++;
                a/=x;
            }
        }
        if(a!=1)cnta++;
        for(auto x:v)
        {
            if(x*x>b)break;
            while( b%x==0)
            {
                cntb++;
                b/=x;
            }
        }
        if(b!=1)cntb++;
        if(cnta+cntb>=k)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

### 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
#include <bits/stdc++.h>

using namespace std;
vector<long long int>v;
long long int p[1000000];
void s()
{
    memset(p,1,sizeof p);
    p[0]=p[1]=0;
    for(long long int i=0;i<=100000;i++)
    {
        if(p[i])
        for(long long int j=i*i;j<=100000;j+=i)
        {
            p[j]=0;
        }
    }
    for(long long int i=0;i<100000;i++)
        if(p[i])v.push_back(i);
}
int main()
{
    s();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int a,b,k;
        scanf("%lld%lld%lld",&a,&b,&k);
        if(k==1)
        {
            if(a==b)
            {
                printf("NO\n");
                continue;
            }
            if(a%b==0 || b%a==0)
            {
                printf("YES\n");
                continue;
            }
            printf("NO\n");
            continue;
        }
        long long int cnta=0,cntb=0;
        for(auto x:v)
        {
            if(x*x>a)break;
            while( a%x==0)
            {
                cnta++;
                a/=x;
            }
        }
        if(a!=1)cnta++;
        for(auto x:v)
        {
            if(x*x>b)break;
            while( b%x==0)
            {
                cntb++;
                b/=x;
            }
        }
        if(b!=1)cntb++;
        if(cnta+cntb>=k)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

```