1538_D. Another Problem About Dividing Numbers
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
```python
import math
import sys
sys.setrecursionlimit(10000)
 
def prime_factors(n):
    global gcdNM
    count=0
    while n%2==0:
        gcdNM+=1
        count+=1
        n=n//2
    for i in range(3,int(math.sqrt(n))+1,2):
        while n % i== 0:
            gcdNM+=1
            count+=1
            n=n//i
    if n > 2:
        gcdNM+=1
        count+=1
    return count
        
def gcd(a,b):
    if a==0 or b==0:
        return max(a,b)
    if a>b:
        a%=b
    else:
        b%=a
    return gcd(a,b)

q=int(input())
for _ in range(q):
    gcdNM=0
    n,m,numTimes=map(int,input().split())
    if m>n:
        n,m=m,n
    godNM=gcd(n,m)
    prime_factors(n//godNM)
    prime_factors(m//godNM)
    #print(gcdNM)
    #print(godNM)
    second=prime_factors(godNM)
    gcdNM+=second
    #print(gcdNM)
    if 1<=numTimes<=gcdNM and n!=m and n%m==0:
        print("YES")
    elif 2<=numTimes<=gcdNM:
        print("YES")
    else:
        print("NO")
    

```