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:
from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce




def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def solve(adj, colors, n):
    pass


def root(parent, a):
    while parent[a] != a:
        parent[a] = parent[parent[a]]
        a = parent[a]
    return a


def union(parent, size, a, b):
    roota, rootb = root(parent, a), root(parent, b)
    if roota == rootb:
        return
    parent[rootb] = roota
    size[roota] += size[rootb]
    size[rootb] = 0


def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


if __name__ == "__main__":
    for i in range(iinput()):
        n=iinput()
        temp1=factors(n)
        temp=list(factors(n))
        temp.sort()
        l=len(temp)
        flag=True
        for i in range(1,l-1):
            for j in range(i+1,l-1):
                if n%(temp[i]*temp[j])==0:
                    s=n/(temp[i]*temp[j])
                    if s!=temp[i] and s!=temp[j] and s!=1 and s!=n and s in temp1:
                        print('YES')
                        print(temp[i],temp[j],int(s))
                        flag=False
                        break
            if not flag:break
        if flag:
            print('NO')