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.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class PrimeFactorization {

    private static List<Integer> primes = new ArrayList();


    // Prepoulates the primes array with all prime numbers uptil N.
    private static void prepopulatePrimes(int N) {
        BitSet isPrime = new BitSet();
        isPrime.set( 0, false);
        isPrime.set( 1, false );

        isPrime.set( 2, N, true );


        for (int i=2; i*i<N; i++ ) {
            if (isPrime.get( i )) {
                for( int j=i*i; j<N; j+=i )
                {
                    isPrime.clear( j );
                }
            }
        }
        for (int i=0; i<N; i++) {
            if (isPrime.get(i)) {
//                System.out.println(i);
                primes.add(i);
            }
        }
//        System.out.println(count);

    }

    // Uses the prepopulated primes array to factorize N.
    public static List<Long> primeFactors(long N) {
        List<Long> factors = new ArrayList<>();
        if (N==0) {
            factors.add(0L);
            return factors;
        }
        if (N==1) {
            factors.add(1L);
            return factors;
        }

        for (long prime : primes) {
            while( N%prime == 0 ) {
                factors.add(prime);
                N = N/prime;
            }
        }
        if (N!=1) {
            factors.add(N);
        }

        for (long x : factors) {
//            System.out.print(x + " ");
        }
//        System.out.println();
        return factors;
    }


    public static void main( String[] args ) throws Exception {
        int MAX = 100000 + 1;
        prepopulatePrimes(MAX);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t=0; t<T; t++) {
            long X = Long.parseLong(br.readLine());
            List<Long> factors = primeFactors(X);
            if (factors.size() <= 2) {
                System.out.println("NO");
            } else {
                long a = factors.get(0);
                long b_part = 1;
                int index = 1;
                boolean fail = false;
                while ((b_part == 1) || (b_part == a)) {
                    if (index >= factors.size()) {
                        fail = true;
                        break;
                    }
                    b_part = b_part * factors.get(index);
                    index++;
                }
                long c_part = 1;
                while (true) {
                    if (index >= factors.size()) {
                        break;
                    }
                    c_part = c_part * factors.get(index);
                    index++;
                }
                if (fail || (c_part == a) || (c_part == b_part) || (c_part == 1)) {
                    System.out.println("NO");
                } else {
                    System.out.println("YES");
                    System.out.println(a + " " + b_part + " " + c_part);
                }
            }
        }

    }
}