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 PYTHON3):

Solution:
import sys
 
# inf = open('input.txt', 'r')
# reader = (line.rstrip() for line in inf)
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
 
t = int(input())
for _ in range(t):
    n = int(input())
    primes = {}
    if not n & 1:
        primes[2] = 0
        while not n & 1:
            n >>= 1
            primes[2] += 1
    f = 3
    lim = int(n ** 0.5) + 1
    while f < lim and f <= n:
        if n % f == 0:
            primes[f] = 0
            while n % f == 0:
                n //= f
                primes[f] += 1
        f += 2
    if n > 1:
        primes[n] = 1
    if len(primes) > 2:
        ans = []
        f = 1
        i = 0
        for i, (k, p) in enumerate(primes.items()):
            f *= pow(k, p)
            if i < 2:
                ans.append(f)
                f = 1
        ans.append(f)
        print('YES')
        print(*ans)
    elif len(primes) == 1:
        for k, p in primes.items():
            if p > 5:
                ans = [k, k * k, pow(k, p-3)]
                print('YES')
                print(*ans)
            else:
                print('NO')
    else:
        powers = sum(primes.values())
        if powers > 3:
            fs = []
            for k, p in primes.items():
                fs.extend([k] * p)
            ans = []
            if fs[0] != fs[1]:
                ans.append(fs[0])
                ans.append(fs[1])
                rest = 2
            else:
                ans.append(fs[0])
                ans.append(fs[1] * fs[2])
                rest = 3
            c = 1
            for f in fs[rest:]:
                c *= f
            ans.append(c)
            print('YES')
            print(*ans)
        else:
            print('NO')
 
# inf.close()