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:
import java.io.*;
import java.util.*;
import java.lang.Math.*;
public class CodeForces615C {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.valueOf(br.readLine());
        for (int i = 0;i<t ;i++ ){
            Number n = new Number(Integer.valueOf(br.readLine()));
            System.out.println(n.tutorialSolution());
        }
    }
}
class Number{
    int input ;
    public Number(int input){
        this.input = input;
    }
    public String tutorialSolution(){
        int a = findSmallestFactor(2,input);
        if(a<=0){
            return "NO";
        }
        int b = findSmallestFactor(a+1, input/a);
        if(b<0){
            return "NO";
        }
        //System.out.println(a+" "+b+" "+input/(a*b));
        StringBuilder sb = new StringBuilder();
        if(input/(a*b)==1){
            sb.append("NO");
        } else{
            if(a!=b && b!= input/(a*b) && a!=input/(a*b)){
                sb.append("YES\n");
                sb.append(a+" "+b+" "+input/(a*b));
            }else {
            	sb.append("NO");
            }
        }
        return sb.toString();
    }
    public int findSmallestFactor(int start, int input){//complexity root(n) same as primes
        int ret = -1;
        double a = (double)input;
        for (int i = start; i<=java.lang.Math.sqrt(a); i++) {
        	//System.out.println(i+" "+ i*i);
            if(input%i==0){
                ret=  i;
                break;
            }
        }
        return ret;
        
    }
    public String findThreeFactors(){
        int [] ret = new int[6];
        int k = input;
        boolean noMoreFactors = false;
        Factors f = null;
        int i = 0;
        for ( i = 0;i<ret.length ;i++ ) {
            f = returnFactors(k);
        	//System.out.println("k " + k + "("+f.a+" "+f.b +")");
            ret[i] = f.a;
            if(f.b<0|| f.b == 1){
            	i++;
                noMoreFactors = true;
                break;
            }
            k = f.b;
        }//what happens when 1 is given
        String retString = null;
        Set<Integer> s  = new HashSet<Integer>();
        if(!noMoreFactors){
            s.add(ret[0]);
            s.add(ret[1]* ret[2]);
            s.add(ret[3]* ret[4]* ret[5]*f.b);
        }else{
            if(i<3){
                retString = "NO";
            }
            if(i==3){
                s.add(ret[0]);
                s.add(ret[1]);
                s.add(ret[2]);
            } else if(i==4){
                s.add(ret[0]);
                s.add(ret[1]* ret[2]);
                s.add(ret[3]);
            } else if(i==5){
                s.add(ret[0]);
                s.add(ret[1]* ret[2]);
                s.add(ret[3]* ret[4]);
            }else if(i==6) {
                s.add(ret[0]);
                s.add(ret[1]* ret[2]);
                s.add(ret[3]* ret[4]* ret[5]);
            }
        }
        if(s.size()==3){
        	StringBuilder sb = new StringBuilder();
        	sb.append("YES\n");
        	Iterator iter = s.iterator();
        	while (iter.hasNext()) {
				sb.append(iter.next());
				if(iter.hasNext()) {
					sb.append(" ");
				}
				
			}
            retString = sb.toString();
             
        } else{
            retString = "NO";
        }
        return retString ;
    }
    public Factors returnFactors(int i){
        if(i==1)
            return new Factors(-1) ;
        if(i==3)
            return new Factors(3) ;
        if(i==2)
            return new Factors(2) ;
        if(i%2==0){
            Factors f = new Factors(i/2, 2);
            return f;
        }
        if(i%3 ==0){
            Factors f = new Factors(i/3, 3);
            return f;
        }
        int j =5;
        while(j<= java.lang.Math.sqrt((double)i) ){// ignore ones where j * j = i
            if(i%j == 0){
                Factors f = new Factors(i/j, j);
                return f;
            } else if(i%(j+2)==0){
                Factors f = new Factors(i/(j+2), j+2);
                return f;
            }
//            System.out.println(j+" "+ (j+2));
            j = j+6;
        }
        return new Factors(i);
    }
    
}
class Factors{
    int a; 
    int b;
    public Factors(int i,int j){
        //make sure a<b and dont add 1
        if(i==1){
            a = j;
            b = -1;
        }else if(j==1){
            a = i;
            b = -1;
        }else if(i<j){
            a = i;
            b = j;
        }else{
            a = j;
            b = i;
        }
    }  
    public Factors(int i){
        a = i;
        b = -1;
    }  
}