#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 4e4 + 10;
const int N = 6e5 + 10;
const ll mod = 1e9 + 7;

int T, prime[maxn], cnt;
bool vis[maxn];
ll a, b, k;

void prepare() {
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt && 1ll * i * prime[j] < maxn; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0)break;
        }
    }
}

int main() {
#ifdef Fly
    freopen("1.txt", "r", stdin);
#endif
    prepare();
    scanf("%d", &T);
    while (T--) {
        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");
            } else {
                printf("No\n");
            }
        } else {
            int num = 0;
            for (int i = 1; i <= cnt && 1ll * prime[i] * prime[i] <= a; ++i) {
                if (a % prime[i] == 0) {
                    while (a % prime[i] == 0) {
                        ++num;
                        a /= prime[i];
                    }
                }
            }
            if (a != 1)++num;
            for (int i = 1; i <= cnt && 1ll * prime[i] * prime[i] <= b; ++i) {
                if (b % prime[i] == 0) {
                    while (b % prime[i] == 0) {
                        ++num;
                        b /= prime[i];
                    }
                }
            }
            if (b != 1)++num;
            if (num >= k) {
                printf("Yes\n");
            } else {
                printf("No\n");
            }
        }
    }
    return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

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;
typedef long long ll;
const int maxn = 4e4 + 10;
const int N = 6e5 + 10;
const ll mod = 1e9 + 7;

int T, prime[maxn], cnt;
bool vis[maxn];
ll a, b, k;

void prepare() {
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt && 1ll * i * prime[j] < maxn; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0)break;
        }
    }
}

int main() {
#ifdef Fly
    freopen("1.txt", "r", stdin);
#endif
    prepare();
    scanf("%d", &T);
    while (T--) {
        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");
            } else {
                printf("No\n");
            }
        } else {
            int num = 0;
            for (int i = 1; i <= cnt && 1ll * prime[i] * prime[i] <= a; ++i) {
                if (a % prime[i] == 0) {
                    while (a % prime[i] == 0) {
                        ++num;
                        a /= prime[i];
                    }
                }
            }
            if (a != 1)++num;
            for (int i = 1; i <= cnt && 1ll * prime[i] * prime[i] <= b; ++i) {
                if (b % prime[i] == 0) {
                    while (b % prime[i] == 0) {
                        ++num;
                        b /= prime[i];
                    }
                }
            }
            if (b != 1)++num;
            if (num >= k) {
                printf("Yes\n");
            } else {
                printf("No\n");
            }
        }
    }
    return 0;
}
```