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:
def read_ints(): return map(int, input().split())


def read_int(): return int(input())


def factors(n):
    factors_p = dict()
    twos = 0
    while n % 2 == 0:
        n //= 2
        twos += 1
    if twos > 0:
        factors_p[2] = twos
    d = 3
    while d * d <= n:
        p = 0
        while n % d == 0:
            p += 1
            n //= d
        if p > 0:
            factors_p[d] = p
        d += 2
    if n > 1:
        factors_p[n] = 1
    return factors_p


t = read_int()

for _ in range(t):
    n = read_int()
    primes = factors(n)
    p_sum = 0
    abc = []
    for k, v in primes.items():
        p_sum += v
    if len(primes) < 1:
        print("No")
        continue
    elif len(primes) == 1:
        if p_sum < 6:
            print("No")
            continue
        else:
            print("Yes")
            d = list(primes.keys())[0]
            abc = [d, d ** 2, n // (d ** 3)]

    elif len(primes) == 2:
        psum = 0
        for k, v in primes.items():
            psum += v
        if psum < 4:
            print("No")
            continue
        print("Yes")
        p1, p2 = list(primes.keys())[:2]
        abc = [p1, p2, n // (p1 * p2)]

    elif len(primes) >= 3:
        print("Yes")
        p1, p2 = list(primes.keys())[:2]
        abc = [p1, p2, n // (p1 * p2)]

    print(*abc)