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.util.ArrayList;
import java.util.Scanner;

public class ProductofThreeNumbers {
	
	public static ArrayList<Integer> factors;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		while (t-- > 0) {
			int n = in.nextInt();
			getFactors(n);
			//brute force 
			boolean found = false;
			for (int i=0;i<factors.size()-2;i++) {
				for (int j=i+1;j<factors.size()-1;j++) {
					for (int k=j+1;k<factors.size();k++) {
						if ((factors.get(i) * factors.get(j) * factors.get(k)) == n) {
							//print the numbres
							System.out.println("YES");
							System.out.println(factors.get(i) + " " + factors.get(j) + " " + factors.get(k));
							found = true;
							i = factors.size();
							j = factors.size();
							k = factors.size();
							break;
							
						}
					}
				}
			}
			if (!found) {
				System.out.println("NO");
			}

		}
		in.close();

	}

	public static void getFactors(int n) {
		factors = new ArrayList<>();
		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (n % i == 0) 
				factors.add(i);
		}
		int size = factors.size() - 2;
		if (factors.size() == 0) {
			return;
		}
		if (factors.get(size + 1) * factors.get(size + 1) != n) {
			factors.add(n / factors.get(size + 1));
		}
		for (int i=size;i>=0;i--) {
			factors.add(n / factors.get(i));
		}
	}
	
	public static void printFactors() {
		for (int i=0;i<factors.size();i++) {
			System.out.print(factors.get(i) + " ");
		}
		System.out.println();
	}

}