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 Contest1294;

import java.util.*;
import java.lang.*;
import java.io.*;

public class C {
	private static FastReader fr;
	private static OutputStream out;
	private static int mod = (int)(1e9+7);
	
	private void solve() {
		int t = fr.nextInt();
		while(t-- > 0) {
			long n = fr.nextLong();
			ArrayList<Long> factors = factors(n);
			if(factors.size() < 3) {
				println("NO");
				continue;
			}
			
			Collections.sort(factors);
			boolean bool = false;
			long a = factors.get(0);
			long b = 1;
			long c = 1;
//			for(long val: factors) {
//				print(val + " ");
//			}
			
			for(int i=1;i<factors.size();i++) {
				b = factors.get(i);
				if(n % (b * a) == 0) {
					c = n / (a * b);
				}else {
					c = 1;
				}
				if(a > 1 && b > 1 && c > 1 && a != b && a != c && b != c && a * b * c == n) {
					bool = true;
					break;
				}
			}
			
			if(bool) {
				println("YES");
				println(a + " " + b + " " + c);
			}else {
				println("NO");
			}
		}
	}
	
	public ArrayList<Long> factors(long num){
		ArrayList<Long> arr = new ArrayList<>();
		for(long i=2;i*i<=num;i++) {
			if(num % i == 0) {
				arr.add(i);
				if(num / i != i) {
					arr.add(num / i);
				}
			}
		}
		return arr;
	}
	
	public static void main(String args[]) throws IOException{
		new C().run();
	}
	
	private ArrayList<Integer> factors(int n, boolean include){
		ArrayList<Integer> factors = new ArrayList<>();
		if(n < 0)
			return factors;
		
		if(include) {
			factors.add(1);
			if(n > 1)
				factors.add(n);
		}
		
		int i = 2;
		for(;i*i<n;i++) {
			if(n % i == 0) {
				factors.add(i);
				factors.add(n / i);
			}
		}
		
		if(i * i == n) {
			factors.add(i);
		}
		
		return factors;
	}
	
	private ArrayList<Integer> PrimeFactors(int n) {
	    ArrayList<Integer> primes = new ArrayList<>();
	 
	    int i = 2;
	    while (i * i <= n) {
	      if (n % i == 0) {
	        primes.add(i);
	 
	        while (n % i == 0) {
	          n /= i;
	        }
	      }
	 
	      i++;
	    }
	 
	    if (n > 1) {
	      primes.add(n);
	    }
	 
	    return primes;
	  }
	
	private boolean isPrime(int n) {
		if(n == 0 || n == 1) {
			return false;
		}
		
		if(n % 2 == 0) {
			return false;
		}
		
		for(int i=3;i*i<=n;i+=2) {
			if(n % i == 0) {
				return false;
			}
		}
		
		return true;
	}

	private ArrayList<Integer> Sieve(int n){
		boolean bool[] = new boolean[n+1];
		Arrays.fill(bool, true);
		bool[0] = bool[1] = false;
		
		for(int i=2;i*i<=n;i++) {
			if(bool[i]) {
				int j = 2;
				while(i*j <= n) {
					bool[i*j] = false;
					j++;
				}
			}
		}
		
		ArrayList<Integer> primes = new ArrayList<>();
		for(int i=2;i<=n;i++) {
			if(bool[i])
				primes.add(i);
		}
		
		return primes;
	}
	
	private HashMap<Integer, Integer> addToHashMap(HashMap<Integer, Integer> map, int arr[]){
		for(int val: arr) {
			if(!map.containsKey(val)) {
				map.put(val, 1);
			}else {
				map.put(val, map.get(val) + 1);
			}
		}
		return map;
	}
	
	private int factorial(int n) {
		long fac = 1;
		for(int i=2;i<=n;i++) {
			fac *= i;
			fac %= mod;
		}
		return (int)(fac % mod);
	}

	private static int pow(int base,int exp){
		if(exp == 0){
			return 1;
		}else if(exp == 1){
			return base;
		}
		int a = pow(base,exp/2);
		a = ((a % mod) * (a % mod)) % mod;
		if(exp % 2 == 1) {
			a = ((a % mod) * (base % mod));
		}
		return a;
	}

	private static int gcd(int a,int b){
		if(a == 0){
			return b;
		}
		
		return gcd(b%a,a);
	}
	
	private static int lcm(int a,int b){
		return (a * b)/gcd(a,b);
	}
	
	private void run() throws IOException{
		fr = new FastReader();
		out = new BufferedOutputStream(System.out);
		solve();
		out.flush();
		out.close();
	}
	
	private static class FastReader{
		private static BufferedReader br; 
		private static StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new BufferedOutputStream(System.out);
		}
		
		public String next() {
			while (st == null || !st.hasMoreElements()) 
			{ 
				try
				{ 
					st = new StringTokenizer(br.readLine()); 
				} 
				catch (IOException e) 
				{ 
					e.printStackTrace(); 
				} 
			} 
			return st.nextToken();
		}
		
		public String nextLine() { 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		 
		public char[] nextCharArray() {
			return next().toCharArray();
		}
		
		public int[] nextIntArray(int n) {
			int arr[] = new int[n];
			for(int i=0;i<n;i++) {
				arr[i] = nextInt();
			}
			return arr;
		}
		
		public long[] nextLongArray(int n) {
			long arr[] = new long[n];
			for(int i=0;i<n;i++) {
				arr[i] = nextLong();
			}
			return arr;
		}
		
		public String[] nextStringArray(int n) {
			String arr[] = new String[n];
			for(int i=0;i<n;i++) {
				arr[i] = next();
			}
			return arr;
		}
		
	}

	public static void print(Object str) {
        try {
            out.write(str.toString().getBytes());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
	
	public static void println(Object str) {
        try {
            out.write((str.toString() + "\n").getBytes());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
	
	public static void println() {
		println("");
	}
	
	public static void printArray(Object str[]){
		for(Object s : str) {
			try {
	            out.write(str.toString().getBytes());
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
		}
	}
}