Problem: You are given one integer number n. Find three distinct integers a, b, c such that 2 ≤ a, b, c and a ⋅ b ⋅ c = n or say that it is impossible to do it.

If there are several answers, you can print any.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 100) — the number of test cases.

The next n lines describe test cases. The i-th test case is given on a new line as one integer n (2 ≤ n ≤ 10^9).

Output

For each test case, print the answer on it. Print "NO" if it is impossible to represent n as a ⋅ b ⋅ c for some distinct integers a, b, c such that 2 ≤ a, b, c.

Otherwise, print "YES" and any possible such representation.

Example

Input


5
64
32
97
2
12345


Output


YES
2 4 8 
NO
NO
NO
YES
3 5 823 

Solution (in JAVA):

Solution:
// package Div3_615;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;

public class ProblemC {
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int test=Integer.parseInt(br.readLine());
        int seive[]=new int[100001];
        ArrayList<Integer> primes=new ArrayList<>();
        for(int i=2;i<=100000;i++){
            if(seive[i]==0){
                primes.add(i);
                for(int j=2*i;j<=100000;j+=i){
                    seive[j]=1;
                }
            }
        }
        StringBuilder print=new StringBuilder();
//        System.out.println(primes.size());
        while(test--!=0){
            int n=Integer.parseInt(br.readLine());
            HashMap<Integer,Integer> power=new HashMap<>();
            int temp=n;
            for(int i=0;i<primes.size();i++){
                int prime=primes.get(i);
                int count=0;
                while(temp%prime==0){
                    count++;
                    temp/=prime;
                }
                if(count!=0){
                    power.put(prime,count);
                }
                if(temp==1){
                    break;
                }
            }
            if(temp!=1){
                power.put(temp,1);
            }
//            System.out.println(power.toString());
            if(power.size()==1){
                for(int k:power.keySet()){
                    if(power.get(k)<6){
                        print.append("NO\n");
                    }
                    else{
                        print.append("YES\n");
                        int a=(int)Math.pow(k,1);
                        int b=(int)Math.pow(k,2);
                        int c=(int)Math.pow(k,power.get(k)-3);
                        print.append(a+" "+b+" "+c+"\n");
                    }
                }
            }
            else if(power.size()==2){
                int pow1=0,pow2=0;
                int prime1=0,prime2=0;
                for(int k:power.keySet()){
                    if(pow1==0){
                        pow1=power.get(k);
                        prime1=k;
                        continue;
                    }
                    else{
                        pow2=power.get(k);
                        prime2=k;
                    }
                }
                if(pow1>=3||pow2>=3){
                    print.append("YES\n");
                    if(pow1>=3){
                        int a=(int)Math.pow(prime1,1);
                        int b=(int)Math.pow(prime1,pow1-1);
                        int c=(int)Math.pow(prime2,pow2);
                        print.append(a+" "+b+" "+c+"\n");
                    }
                    else{
                        int a=(int)Math.pow(prime2,1);
                        int b=(int)Math.pow(prime2,pow2-1);
                        int c=(int)Math.pow(prime1,pow1);
                        print.append(a+" "+b+" "+c+"\n");
                    }
                }
                else if(pow1==2&&pow2==2){
                    print.append("YES\n");
                    int a=(int)Math.pow(prime1,1);
                    int b=(int)Math.pow(prime2,1);
                    int c=a*b;
                    print.append(a+" "+b+" "+c+"\n");
                }
                else{
                   print.append("NO\n");
                }
            }
            else{
                int a=0,b=0,c=1;
                for(int k:power.keySet()){
                    if(a==0){
                        a=(int)Math.pow(k,power.get(k));
                        continue;
                    }
                    if(b==0){
                        b=(int)Math.pow(k,power.get(k));
                        continue;
                    }
                    int t=(int)Math.pow(k,power.get(k));
                    c*=t;
                }
                print.append("YES\n");
                print.append(a+" "+b+" "+c+"\n");
            }
        }
        System.out.println(print.toString());
    }
}