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 math
for _ in range(int(input())):
	n = int(input())
	dic = {}
	x = n
	if x%2==0:
		dic[2] = 0
		while x%2==0:
			x//=2
			dic[2] += 1
	for i in range(3,int(math.sqrt(x))+1,2):
		if x%i==0:
			dic[i] = 0
			while x%i==0:
				x//=i 
				dic[i] += 1
	if x>2:
		dic[x] = 1

	# print(dic)

	if len(dic)==3:
		print('YES')
		ans = []
		for i in dic:
			ans += [pow(i,dic[i])]
		print(*ans)
	elif len(dic)>3:
		print('YES')
		ans = []
		c = 0
		for i in dic:
			ans += [pow(i,dic[i])]
			c+=1
			dic[i] = 0
			if c==3:
				break
		t = 1
		for i in dic:
			t*= pow(i,dic[i])
		ans[-1]*=t
		print(*ans)
	elif len(dic)==2:
		s = 0
		for i in dic:
			s+=dic[i]
		if s>=4:
			print('YES')
			ans = []
			b = 1
			for i in dic:
				ans += [i]
				b*= pow(i,dic[i]-1)
			ans+=[b]
			print(*ans)
		else:
			print('NO')
	else:
		for i in dic:
			if dic[i]>=6:
				print('YES')
				print(i,pow(i,2),pow(i,dic[i]-3))
			else:
				print('NO')