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.*;
import java.io.*;
import java.math.*;

public class Main
{

    final static int mod = 1000000007;
    static FastReader sc;
    static PrintWriter out;
    static boolean test_case_input = true;

    public static void solution() throws IOException
    {
        int n = sc.nextInt();
        int a = -1, b = -1, c = -1;
        int temp = n;
        for(int i=2; (long) i*i <= temp; i++) {
            if(n == 1) break;
            if(n % i == 0) {
                if(a == -1) {
                    a = i;
                    n /= i;
                }
                while(n % i == 0) {
                    if(b == -1) {
                        b = i;
                        n /=i;
                    }
                    else if(b == a) {
                        b *= i;
                        n /= i;
                    }
                    else {
                        if(c == -1) {
                            c = i;
                            n /=i;
                        }
                        else {
                            c *= i;
                            n /= i;
                        }
                    }
                }
            }
        }
        if(n != 1) {
            if(c == -1) c = n;
            else c *= n;
        }
        if(a != b && b != c && a != c && a != -1 && b != -1 && c != -1) {
            out.println("YES\n" + a + " " + b + " " + c);
        }
        else out.println("NO");
    }

    // GCD
    public static int __gcd(int a, int b)
    {
        BigInteger n1 = BigInteger.valueOf(a);
        BigInteger n2 = BigInteger.valueOf(b);
        BigInteger gcd = n1.gcd(n2);
        return gcd.intValue();
    }

    public static long __gcd(long a, long b)
    {
        BigInteger n1 = BigInteger.valueOf(a);
        BigInteger n2 = BigInteger.valueOf(b);
        BigInteger gcd = n1.gcd(n2);
        return gcd.longValue();
    }

    public static void main(String args[]) throws IOException
    {
        long start = 0, end = 0;
        try
        {
            File output = new File("output.txt");
            sc = new FastReader();
            if (output.exists())
            {
                out = new PrintWriter(new FileOutputStream("output.txt"));
                start = System.nanoTime();
            } else
            {
                out = new PrintWriter(System.out);
            }

            int test_cases = 1;
            if (test_case_input) test_cases = sc.nextInt();
            while (test_cases-- > 0)
            {
                solution();
            }
            if (output.exists())
            {
                end = System.nanoTime();
                out.println("Execution time: " + (end - start) / 1000000 + " ms");
            }
            out.flush();
            out.close();
        } catch (Exception e)
        {
            out.println("Exception: " + e);
            out.flush();
            out.close();
            return;
        }
    }

    // Fast IO
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() throws FileNotFoundException
        {
            File in = new File("input.txt");
            if (in.exists())
            {
                br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
            } else
            {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        float nextFloat()
        {
            return Float.parseFloat(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            } catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}