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 in=new Scanner(System.in);
        int t=in.nextInt();
        for(int i=0;i<t;i++){
            int n=in.nextInt();
            int lasttemp=1;
            List<Integer> res=new ArrayList<>();
            for(int temp=2;temp<=Math.sqrt(n)&&n!=1;temp++) {
                while (n%temp==0) {
                        res.add(temp);
                        n /= temp;
                }
            }
            if(n!=1) res.add(n);
            List<Integer> integers = get(res);
            if(integers.size()>2) {
                System.out.println("YES");
                System.out.println(integers.get(0) + " " + integers.get(1) + " " + (integers.get(2) * (integers.size()>3?integers.get(3):1)));
            }else
                System.out.println("NO");
        }
    }
    public static  List<Integer> get(List<Integer> list){
        List<Integer> res=new ArrayList<>();
        int cur=1;
        int i;
        for(i=0;i<list.size()&&res.size()<3;i++){
            cur*=list.get(i);
            int j=0;
            for(;j<res.size();j++)if(res.get(j)==cur)break;
            if(j==res.size()){
                res.add(cur);cur=1;
            }
        }
        int temp=1;
        for(int j=i;j<list.size();j++)temp*=list.get(j);
        if(temp!=1)
        res.add(temp);
        return res;
    }
}