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.*;

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

        int T  = sc.nextInt();

        //make(T);;
        while (T-->0)
        {
            int N = sc.nextInt();
            HashSet<Long> values = new HashSet<>();
            values.add(1l);
            long current_i = 1 ;
            int sqrt = (int)Math.sqrt(N);
            for(int i = 2 ; i <= sqrt && values.size()<3; i++)
            {
                while (N>0 && N%i==0 && values.size()<3)
                {
                    if(!values.contains(current_i))
                    {
                        values.add(current_i);
                        current_i = 1;
                    }else {
                        current_i*=i;
                        N/=i;
                    }
                    if(N==0)
                        break;
                }


            }
            if(!values.contains(current_i))
                values.add(current_i);
            if(N > 1)
                values.add((long)N);
            values.remove(1l);

            if(values.size()<3)
            {
                System.out.println("NO");
            }else {
                TreeSet<Long> set = new TreeSet<>(values);
                while(set.size()>3)
                {
                    set.add(set.pollLast()*set.pollLast());
                }

                StringBuilder bw = new StringBuilder();
                System.out.println("YES");
                for (long a :
                        set) {
                    bw.append(a+" ");
                }
                bw.deleteCharAt(bw.length()-1);
                System.out.println(bw);
            }
        }
    }
    private static boolean bf(int a)
    {
        for(int i = 2  ; i < a ;i++)
        {
            for(int j = i+1 ; j < a ;j++)
            {

                int ab = i*j;
                int dev = a/ab;
                if(a%ab==0 && dev!=i && dev>j)
                {
                    return true;
                }

            }
        }
        return false;
    }

}