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

public class C {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();

        for (int test = 0; test < t; test++) {
            n = in.nextLong();
            long original = n;

            //TreeSet<Long> factors = factors(n);
            //TreeSet<Long> res = new TreeSet();

            TreeSet<Long> res = factors2(n);

            for (long x: res){
                original/=x;
            }

            if (original == 1 && res.size()==3){
                System.out.println("YES");
                for (long x: res){
                    System.out.print(x+" ");
                }
                System.out.println();
            }
            else System.out.println("NO");



//            if (factors.size()>2) {
//                long smallestDiv = factors.pollFirst();
//                res.add(smallestDiv);
//                n /= smallestDiv;
//
//                for (Long x : factors) {
//                    if (!res.contains(x)) {
//                        if (factors.contains(n / x)) {
//                            res.add(x);
//                            res.add(n / x);
//                            break;
//                        }
//                    }
//                }
//
//                if (res.size()==3){
//                    System.out.println("YES");
//                    for (long val: res){
//                        System.out.print(val+" ");
//                    }
//                    System.out.println();
//                }
//                else System.out.println("NO");
//            }else System.out.println("NO");

        }
    }
    static long n;
    public static TreeSet<Long> factors2(long n) {

        long original = n;
        TreeSet<Long> list = new TreeSet<>();
        for (int i = 2; i <= Math.sqrt(original); i++) {
            if (n % i == 0) {
                if (!list.contains((long)i)){
                    list.add((long)i);
                    n/=i;
                }
                if (list.size()==2){
                    if (original % n == 0){
                        list.add(n);
                        break;
                    }
                }
            }
        }
        //list.add(n);
        return list;
    }

    public static TreeSet<Long> factors(long n) {

        TreeSet<Long> list = new TreeSet<>();
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                if (n / i == i) {
                    list.add((long)i);
                } else {
                    list.add((long)i);
                    list.add(n / i);
                }

            }
        }
        return list;
    }
    static long countTwo = 0;
    public static TreeSet<Long> primeFactors(Long n) {
        ArrayList<Long> list = new ArrayList<>();
        TreeSet<Long> tree = new TreeSet();

        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                if (i == 2)countTwo++;
                tree.add((long)i);
                n /= i;
            }
        }

        if (n > 1) {
            if (n == 2) countTwo++;
            tree.add(n);
        }

        return tree;
    }

}