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

public class Main
{ 	
	public static void main(String[] args)throws Exception
	{
	    Reader reader = new Reader();
		reader.readLine();
		int t = reader.readInt(0);

		StringBuilder res = new StringBuilder();
		while (t-- > 0)
		{
			reader.readLine();
			int num = reader.readInt(0);

			List<List<Integer>> divisors = getDivisors(num);

			boolean found = false;
			for (List<Integer> row:divisors)
			{

				int v1 = row.get(0);
				int v2 = row.get(1);

				List<List<Integer>> v1Div = getDivisors(v1);

				if (isValid(v2, v1Div, res))
				{
					found = true;
					break;
				}

				List<List<Integer>> v2Div = getDivisors(v2);

				if (isValid(v1, v2Div, res))
				{
					found = true;
					break;
				}
			}

			if (!found)
			{
				res.append("NO\n");
			}

			//System.out.println(res);

		}
		System.out.println(res.toString().trim());
		reader.close();
	}

	static List<List<Integer>>  getDivisors(int n) 
	{ 
	    List<List<Integer>> ans = new ArrayList<>();
        for (int i=2; i <= Math.ceil(Math.sqrt(n)); i++) 
		{ 
			if (n % i == 0) 
			{ 
				if (n / i == i)
				{
					if (i != 1 && n / i != 1)
					//System.out.printf("%d ", i);
					ans.add(new ArrayList<>(Arrays.asList(i, i)));
				}
				else
				{

					if (i != 1 && n / i != 1)
					//System.out.printf("%d %d ", i, n / i); 
						ans.add(new ArrayList<>(Arrays.asList(i, n / i)));
				}
			}
		} 
		return ans;
	}

	static boolean isValid(int v, List<List<Integer>> v2Div, StringBuilder ans)
	{

		for (List<Integer> row:v2Div)
		{
			int v1 = row.get(0);
			int v2 = row.get(1);

			if (v != v1 && v != v2 && v1 != v2)
			{
				ans.append("YES\n").
					append(String.format("%d %d %d\n", v, v1, v2));
				return true;
			}
		}
		return false;
	}

}

class Pair
{
	int index;
	int level;

	public Pair(int index, int level)
	{
		this.index = index;
		this.level = level;
	}

	@Override
	public String toString()
	{
		return index + " " + level;
	}

}

class Reader
{     
    private BufferedReader reader; 
    private String line[];     

    public Reader()     
    {         
        reader = new BufferedReader(new InputStreamReader(System.in));     
    }     

    public String[] getLine()     
    {         
        return line;     
    }     

    public boolean readLine()     throws IOException 
    {         
        String str = reader.readLine();
        if (str == null || str.isEmpty())
            return false;
        line = line = str.split(" ");
        return true;
    }    

    public List<Integer> getIntegersList()
    {
        List<Integer> res = new ArrayList<>();
        for (String str:line)
            res.add(Integer.parseInt(str));
        return res;

    }

	public Set<Integer> getIntegersSet()
    {
        Set<Integer> res = new HashSet<>();
        for (String str:line)
            res.add(Integer.parseInt(str));
        return res;

    }

	public List<Long> getLongsList()
    {
        List<Long> res = new ArrayList<>();
        for (String str:line)
            res.add(Long.parseLong(str));
        return res;

    }

    public int readInt(int pos)throws IOException     
    {         
        return Integer.parseInt(line[pos]);     
    }     

    public double readDouble(int pos)throws IOException     
    {         
        return Double.parseDouble(line[pos]);     
    }     

    public long readLong(int pos)throws IOException 
    {         
        return Long.parseLong(line[pos]); 
    }     

    public String readString(int pos)throws IOException     
    {         
        return line[pos];     
    }     

    public void close()throws IOException 
    {         
        reader.close();     
    }
}