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:
////////////////////---------------------------SHUBHAM CHAUDHARI-------------------------------///////////////////////


import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner in=new Scanner(System.in);
        int t=in.nextInt();
        StringBuilder res=new StringBuilder();
        while (t-->0)
        {
            int n=in.nextInt();
            ArrayList<Integer>primes=primeFactors(n);
            HashSet<Integer>set=new HashSet<>();
            for(int i=0;i<primes.size();i++)
            {
                set.add(primes.get(i));
            }
            primes=new ArrayList<>();
            for(int i:set)
            {
                primes.add(i);
            }
            int tmp=n;
            int size=0;
            for(int i=0;i<primes.size();i++)
            {
                while (tmp%primes.get(i)==0)
                {
                    tmp/=primes.get(i);
                    size++;
                }
            }
            //System.out.println(primes.size());
            if(primes.size()==1)
            {
                if(size>=6)
                {
                    res.append("YES\n");
                    //System.out.println("ji");
                    res.append(primes.get(0)+" "+(primes.get(0)*primes.get(0))+" "+(n/(primes.get(0)*primes.get(0)*primes.get(0)))+"\n");
                }
                else
                    res.append("NO\n");
            }
            else if(primes.size()==2)
            {
                if(size>3)
                {
                    res.append("YES\n");
                    res.append(primes.get(0)+" "+primes.get(1)+" "+(n/(primes.get(0)*primes.get(1)))+"\n");
                }
                else
                {
                    res.append("NO\n");
                }
            }
            else
            {
                res.append("YES\n");
                res.append(primes.get(0)+" "+primes.get(1)+" "+(n/(primes.get(0)*primes.get(1)))+"\n");
            }
        }
        System.out.println(res);

    }
    public static ArrayList<Integer> primeFactors(int n)
    {
        ArrayList<Integer>list=new ArrayList<>();
        while (n%2==0)
        {
            list.add(2);
            n /= 2;
        }

        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            while (n%i == 0)
            {
                list.add(i);
                n /= i;
            }
        }
        if (n > 2)
            list.add(n);
        return list;
    }

    static class Node implements Comparable<Node>
    {
        int x;
        int y;


        public Node(int x,int y)
        {
            this.x=x;
            this.y=y;
        }


        @Override
        public int compareTo(Node o) {
            if(x>o.x)
            {
                return 1;
            }
            if(x==o.x)
            {
                if(y>o.y)
                    return 1;
                else if(y<o.y)return -1;
                return 0;
            }
            return -1;
        }
    }

}