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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main{

   static FastReader fs=new FastReader();
   static class FastReader{
      BufferedReader br;
      StringTokenizer st;
      public FastReader(){
         br = new BufferedReader(new InputStreamReader(System.in));
      }
      String next(){
         while (st == null || !st.hasMoreElements()){
            try{
               st = new StringTokenizer(br.readLine());
            }catch (IOException e){
               e.printStackTrace();
            }
         }
         return st.nextToken();
      }
      int nextInt(){
         return Integer.parseInt(next());
      }
      long nextLong(){
         return Long.parseLong(next());
      }
      double nextDouble(){
         return Double.parseDouble(next());
      }
      String nextLine(){
         String str = "";
         try{
            str = br.readLine();
         }catch (IOException e){
            e.printStackTrace();
         }
         return str;
      }

      int[] inputIntArray(int n){
         int[] arr = new int[n];
         for(int i=0;i<n;i++)
            arr[i] = fs.nextInt();

         return arr;
      }
   }

   static class Pair{
      char f;
      Character s ;

      public Pair(char f, Character s) {
         this.f = f;
         this.s = s;
      }
   }

   static class TreeNode{
      int id;
      ArrayList<Integer> children;

      TreeNode(int id){
         this.id = id;
         this.children = new ArrayList<>();
      }
   }
    /*
    const ll mod = 7901;

    ll modulo(ll x)
    {
        return (x % mod + mod) % mod;
    }

    ll mul(ll x,ll y)
    {
        return modulo( modulo(x) * modulo(y) );
    }

    ll add(ll x,ll y)
    {
        return modulo( modulo(x) + modulo(y) );
    }

    ll sub(ll x,ll y)
    {
        return modulo(modulo(x) + modulo(-y));
    }*/

   static ArrayList<Integer> primeList = new ArrayList<>();
   static Boolean[] isPrime = new Boolean[100001];
   static void preCalculatePrimeList(){
      isPrime[0] = false;
      isPrime[1] = false;

      for(int i=2;i<=100000;i++){
         if(isPrime[i] == null){
            isPrime[i] = true;
            primeList.add(i);
            for(int j=i*2;j <= 100000 ;j += i){
               isPrime[j] = false;
            }
         }
      }
   }
   static void sortIntArray(int[] arr){
      ArrayList<Integer> al = new ArrayList<>();
      for(int val : arr){
         al.add(val);
      }

      Collections.sort(al);
      for(int i=0;i<arr.length;i++){
         arr[i] = al.get(i);
      }
   }
   static StringBuffer[][] dp;
   public static void main(String[] args){
      int t = 1;
      t = fs.nextInt();
      preCalculatePrimeList();
      while (t-- > 0){

         int a = fs.nextInt();
         int b = fs.nextInt();
         int k = fs.nextInt();

         int primeA = countPrime(a);
         int primeB = countPrime(b);

         int maxK = primeA + primeB;

         int minK = 2;
         int gcd = gcd(a,b);
         if(gcd == a || gcd == b) minK = 1;
         if(a == b) minK = 0;

         if(k == 1){
            if(minK == 1) System.out.println("YES");
            else System.out.println("NO");
         }
         else if(k >= minK && k <= maxK) System.out.println("YES");
         else System.out.println("NO");

      }
   }

   static int countPrime(int a){
      int count = 0;
      int i = 0;
      int prime = primeList.get(i);
      while(prime * prime <= a){
         if(a % prime == 0){
            while (a % prime == 0){
               count++;
               a /= prime;
            }
         }

         i++;
         if(i < primeList.size())
            prime = primeList.get(i);
         else
            break;
      }

      if(a != 1) count++;

      return count;
   }

   private static int sumOfArray(int[] arr) {
      int sum = 0;
      for(int i=0;i<arr.length;i++)
         sum += arr[i];

      return sum;
   }

   private static int fun1(int[] arr) {
      int ans = 0;
      for(int i=1;i<arr.length;i++){
         if(arr[ans] > arr[i]){
            ans = i;
         }
      }

      return ans;
   }

   private static int fun2(int[] arr) {
      int ans = 0;
      for(int i=1;i<arr.length;i++){
         if(arr[ans] < arr[i]){
            ans = i;
         }
      }

      return ans;
   }


   private static StringBuffer findMin(int m, int s) {
      if(m == 1 && s < 10) return new StringBuffer(s+"");
      else if (m ==1) return new StringBuffer(-1+"");

      if(dp[m][s] != null) return dp[m][s];

      for(int i=0;i<s;i++){
         StringBuffer sb = findMin(m-1,s-i);
         if(sb.length() <=2 && Integer.parseInt(sb.toString()) != -1){
            if(i == 0){
               sb.insert(1,"0");
            }
            else{
               sb = sb.reverse();
               sb.append(i);
               sb.reverse();

               ;                }

            dp[m][s] = sb;
            return sb;
         }
      }

      return new StringBuffer("-1");
   }

   private static StringBuffer findMax(int m, int s) {
      if(m == 1 && s < 10) return new StringBuffer(s+"");
      else if (m ==1) return new StringBuffer(-1+"");

      if(dp[m][s] != null) return dp[m][s];

      for(int i=0;i<s;i++){
         StringBuffer sb = findMax(m-1,s-i);
         if(sb.length() <=2 && Integer.parseInt(sb.toString()) != -1)
         {
            sb.append(i);
            dp[m][s] = sb;
            return sb;
         }
      }

      return new StringBuffer("-1");
   }

   private static int lcm(int a, int b) {
      int gcd = gcd(a,b);
      return (int)((long)a*(long)b)/gcd ;
   }

   private static void updateMyParentsValue(char[] s, int[] ans, int pos) {
      int nom = s.length;

      int parentIdx = (nom-1-pos)/2 + 1 + pos;
      if(parentIdx >= nom) return;

      int hChildIdx = nom - 1 - ((nom-1-parentIdx)*2+1);
      int lChildIdx = hChildIdx - 1;

      if(hChildIdx < 0){
         if(s[parentIdx] != '?') ans[parentIdx] = 1;
         else ans[parentIdx] = 2;
      }
      else {
         if (s[parentIdx] == '1') ans[parentIdx] = ans[hChildIdx];
         else if (s[parentIdx] == '0') ans[parentIdx] = ans[lChildIdx];
         else ans[parentIdx] = ans[hChildIdx] + ans[lChildIdx];
      }

      updateMyParentsValue(s,ans,parentIdx);

   }

   private static void updateMyValue(char[] s, int[] ans, int i) {
      int nom = s.length;

      int hChildIdx = (nom - 1 - ((nom-1-i)*2+1));
      int lChildIdx = hChildIdx - 1;

      if(hChildIdx < 0){
         if(s[i] != '?') ans[i] = 1;
         else ans[i] = 2;
      }
      else {
         if (s[i] == '1') ans[i] = ans[hChildIdx];
         else if (s[i] == '0') ans[i] = ans[lChildIdx];
         else ans[i] = ans[hChildIdx] + ans[lChildIdx];
      }
   }


   private static int[] preprocess(char[] s) {
      int nom = s.length;
      int[] ans = new int[nom];

      for(int i=0;i<nom;i++){
         int hChildIdx = (nom - 1 - ((nom-1-i)*2+1));
         int lChildIdx = hChildIdx - 1;

         if(hChildIdx < 0){
            if(s[i] != '?') ans[i] = 1;
            else ans[i] = 2;
         }
         else{
            if(s[i] == '1') ans[i] = ans[hChildIdx];
            else if(s[i] == '0') ans[i] = ans[lChildIdx];
            else ans[i] = ans[hChildIdx] + ans[lChildIdx];
         }
      }

      return ans;

   }

   private static int gcd(int a, int b) {
      if(b == 0) return a;
      else return gcd(b , a % b);
   }

   static void bubbleSort(int[] arr){
      int n = arr.length;
      for(int i=0;i<n;i++)
      {
         boolean alreadySwapped = true;
         for(int j=n-1;j>i;j--)
         {
            if(arr[j-1]>arr[j])
            {
               int temp = arr[j-1];
               arr[j-1] = arr[j];
               arr[j] = temp;
               alreadySwapped = false;
            }
         }

         if(alreadySwapped) break;
      }
   }

   static void selectionSort(int[] arr){
      int n = arr.length;
      for(int i=0;i<n;i++)
      {
         int smallestElementIndex = i;
         for(int j=i+1;j<n;j++)
         {
            if(arr[j]<arr[smallestElementIndex])
               smallestElementIndex = j;
         }
         int temp = arr[i];
         arr[i] = arr[smallestElementIndex];
         arr[smallestElementIndex] = temp;
      }
   }

   static void insertionSort(int[] arr){
      int n = arr.length;
      for(int i=0;i<n-1;i++)
      {
         int key = arr[i+1];
         int j = i;
         for(j=i;j>=0;j--)
         {
            if (arr[j] > key)
            {
               arr[j + 1] = arr[j];
            }
            else
            {
               break;
            }
         }
         arr[j + 1] = key;
      }
   }

   static Random r = new Random();
   static void quickSort(int[] arr,int start,int end){
      if(start < end){
         int idx = partitionElement(arr,start,end);
         quickSort(arr,start,idx-1);
         quickSort(arr,idx+1,end);
      }
   }

   private static int partitionElement(int[] arr, int start, int end) {
      int rand_pivot = r.nextInt(end-start)+start;
      swap(arr,start,rand_pivot);

      int i = start + 1;
      int j = start + 1;
      int key = arr[start];

      while(i <= end){
         if(arr[i] <= key){
            swap(arr,j,i);
            j++;
         }
         i++;
      }
      swap(arr,start,j-1);
      return j-1;
   }

   private static void swap(int[] arr, int start, int rand_pivot) {
      int temp = arr[start];
      arr[start] = arr[rand_pivot];
      arr[rand_pivot] = temp;
   }
}