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:
//Contribted By - Rahul Roy
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
		public static void main(String sp[])throws IOException{
		FastReader sc = new FastReader();
		int t = sc.nextInt();
		while(t-->0){
			int n = sc.nextInt();
			
			long first = 0;
			long second = 0;
			long third = 0;
			compute(n);
			Collections.sort(al);
			if(hm.size()==0)
				System.out.println("NO");
			else if(hm.size()==1){
				if(al.size()<6){
					System.out.println("NO");
				}else{
					first =  al.get(0);
					second = al.get(1)*al.get(2);
					third = 1;
					for(int i=3;i<al.size();i++)
						third *= al.get(i); 
					System.out.println("YES");
					System.out.println(first+" "+second+" "+third);
				}
			}else if(hm.size()==2){
				if(al.size()<=3)
					System.out.println("NO");
				else{
					first =  al.get(0);
					int index=1;
					second = 1;
					for(int i=index;i<al.size();i++){
						second*=al.get(i);
						index+=1;
						if(first!=second)
							break;
					}
					third = 1;
					for(int i=index;i<al.size();i++)
						third *= al.get(i); 
					System.out.println("YES");
					System.out.println(first+" "+second+" "+third);
				}
			}else{
					first =  al.get(0);
					int index=1;
					second = 1;
					for(int i=index;i<al.size();i++){
						second*=al.get(i);
						index+=1;
						if(first!=second)
							break;
					}
					third = 1;
					for(int i=index;i<al.size();i++)
						third *= al.get(i); 
					System.out.println("YES");
					System.out.println(first+" "+second+" "+third);
			}
			hm = new HashMap<Integer,Integer>();
			al = new ArrayList<Integer>();
		}
	}
	
	
	static ArrayList<Integer> al = new ArrayList<>();
	static HashMap<Integer,Integer> hm = new HashMap<>();
	public static void compute(int n){
		while (n%2==0) 
		{ 
			al.add(2);
			hm.put(2,0);
			n /= 2; 
		} 

		// n must be odd at this point. So we can 
		// skip one element (Note i = i +2) 
		for (int i = 3; i <= Math.sqrt(n); i+= 2) 
		{ 
			// While i divides n, print i and divide n 
			while (n%i == 0) 
			{ 
				al.add(i);
				hm.put(i,0);
				n /= i; 
			} 
		} 
		if(n>2){
			hm.put(n,0);
			al.add(n);
		}

	}
	public static class pair{
		int x =0;
		int y=0;
	}
	
	public static class comp implements Comparator<pair>{
		public int compare(pair o1, pair o2){
			if(o1.x==o2.x)
				return o1.y-o2.y;
			return o1.x-o2.x;
		}
	}

	
	
		
		
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
	
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
}
/* class Triplet{
	int threeSumClosest(ArrayList<Integer> arr, int target) {
        int flag=0,n = arr.size();
        int res=0;
        
        Collections.sort(arr);
		
        for(int i = 0 ; i < n-2 ; ++ i ) {  
            
            int j = i+1, k = n-1;
            
            while(j<k) {
                int sum=arr.get(i)+arr.get(j)+arr.get(k);   // get the sum of the triplet
                
                if(flag==0){  // if its your 1st triplet updated res
                    res=sum;
                    flag=1;
                }
                
                if(Math.abs(sum-target)<=Math.abs(res-target)) {   // compare the difference if sum is closer to target then res
                    if(Math.abs(sum-target)==Math.abs(res-target)){
                        if(res<sum)
                            res=sum;
                    }
                    else
                        res=sum;
                }
                
                if(target>sum)  // if sum is smaller than target
                    j++;
                else        // if sum is greater than target
                    k--;
            }
        }
        return res; // return the answer 
    }
} */