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
import math
from collections import defaultdict
from collections import deque
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : list(map(int, input().split()))
go = lambda : 1/0
def write(*args, sep="\n"):
  for i in args:
    sys.stdout.write("{}{}".format(i, sep))
INF = float('inf')
MOD = int(1e9 + 7)
YES = "YES"
NO = "NO"

def f(n):
  ret, x = defaultdict(int), []
  for i in range(2, int(n**0.5) + 1):
    while n % i == 0:
      ret[i] += 1
      x.append(i)
      n //= i

  if n != 1:
    ret[n] += 1
    x.append(n)
  return ret, x 

for _ in range(int(input())):
  try:
    n = int(input())
    arr, x = f(n)

    if len(arr) >= 3:
      (x, xcnt), (y, ycnt), *c = list(arr.items())
      z = 1 
      for i, j in c:
        z *= (i ** j)
      print(YES)
      print(x**xcnt, y**ycnt, z)
      go()
    
    if len(arr) == 2:
      (x, xcnt), (y, ycnt) = arr.items()
      
      if xcnt + ycnt <= 3:
        print(NO)
        go()
      
      if xcnt == 2 and ycnt == 2:
        print(YES)
        print(x, y, x*y)
        go() 

      if xcnt >= 3:
        print(YES)
        print(x, x**(xcnt - 1), y**ycnt)
        go() 
      
      if ycnt >= 3:
        print(YES)
        print(y, y**(ycnt - 1), x**xcnt)
        go() 
    
    if len(arr) == 1:
      #print("== 1")
      (x, xcnt) = list(arr.items())[0]
      if xcnt <= 5:
        print(NO)
        go() 
      else:
        print(YES)
        print(x, x*x, x**(xcnt - 3)) 
        go() 

  except Exception as e:
    continue