#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <map>
#include <string>
#include <stack>
#include <set>
#include <utility>
#include <bitset>
#include <ctime>
#include <fstream>
//#include <unordered_map>

using namespace std;
int a, b, d, c, f, e, n, m, k, s, bj, c1, c2, c3, max1, min1, tot, prime[100010], num[100010], num2[100010];
bool mp[100010];

int main()
{
    scanf("%d", &s);
    for (a = 2; a <= 32000; ++a)
    {
        if (!mp[a])
        {
            prime[d++] = a;
            for (c = a * a; c <= 32000; c += a)
                mp[c] = true;
        }
    }
    while (s--)
    {
        scanf("%d %d %d", &n, &m, &k);
        int sum = 0;
        e = f = 0;
        for (a = 0; a < d; ++a)
        {
            b = 0;
            while (n % prime[a] == 0)
            {
                b++;
                n /= prime[a];
            }
            num[a] = b;
            sum += b;
            b = 0;
            while (m % prime[a] == 0)
            {
                b++;
                m /= prime[a];
            }
            num2[a] = b;
            sum += b;
            if (num2[a] > num[a])
                f += num2[a] - num[a];
            else
                e += num[a] - num2[a];
        }
        if (n == 1)
        {
            if (m != 1)
            {
                f++;
                sum++;
            }
        }
        else
        {
            if (m == 1)
            {
                e++;
                sum++;
            }
            else
            {
                sum += 2;
                if (n != m)
                {
                    e++;
                    f++;
                }
            }
        }
        if (k > sum)
            printf("NO\n");
        else
        {
            if (k == 1 && ((e != 0 && f != 0) || (e == 0 && f == 0)))
                printf("NO\n");
            else
                printf("YES\n");
        }
    }
    return 0;
}
### Prompt

Please formulate 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 <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <map>
#include <string>
#include <stack>
#include <set>
#include <utility>
#include <bitset>
#include <ctime>
#include <fstream>
//#include <unordered_map>

using namespace std;
int a, b, d, c, f, e, n, m, k, s, bj, c1, c2, c3, max1, min1, tot, prime[100010], num[100010], num2[100010];
bool mp[100010];

int main()
{
    scanf("%d", &s);
    for (a = 2; a <= 32000; ++a)
    {
        if (!mp[a])
        {
            prime[d++] = a;
            for (c = a * a; c <= 32000; c += a)
                mp[c] = true;
        }
    }
    while (s--)
    {
        scanf("%d %d %d", &n, &m, &k);
        int sum = 0;
        e = f = 0;
        for (a = 0; a < d; ++a)
        {
            b = 0;
            while (n % prime[a] == 0)
            {
                b++;
                n /= prime[a];
            }
            num[a] = b;
            sum += b;
            b = 0;
            while (m % prime[a] == 0)
            {
                b++;
                m /= prime[a];
            }
            num2[a] = b;
            sum += b;
            if (num2[a] > num[a])
                f += num2[a] - num[a];
            else
                e += num[a] - num2[a];
        }
        if (n == 1)
        {
            if (m != 1)
            {
                f++;
                sum++;
            }
        }
        else
        {
            if (m == 1)
            {
                e++;
                sum++;
            }
            else
            {
                sum += 2;
                if (n != m)
                {
                    e++;
                    f++;
                }
            }
        }
        if (k > sum)
            printf("NO\n");
        else
        {
            if (k == 1 && ((e != 0 && f != 0) || (e == 0 && f == 0)))
                printf("NO\n");
            else
                printf("YES\n");
        }
    }
    return 0;
}
```