You are given an integer $n$ ($n > 1$).

Your task is to find a sequence of integers $a_1, a_2, \ldots, a_k$ such that:

each $a_i$ is strictly greater than $1$;

$a_1 \cdot a_2 \cdot \ldots \cdot a_k = n$ (i. e. the product of this sequence is $n$);

$a_{i + 1}$ is divisible by $a_i$ for each $i$ from $1$ to $k-1$;

$k$ is the maximum possible (i. e. the length of this sequence is the maximum possible).

If there are several such sequences, any of them is acceptable. It can be proven that at least one valid sequence always exists for any integer $n > 1$.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains one integer $n$ ($2 \le n \le 10^{10}$).

It is guaranteed that the sum of $n$ does not exceed $10^{10}$ ($\sum n \le 10^{10}$).


-----Output-----

For each test case, print the answer: in the first line, print one positive integer $k$ — the maximum possible length of $a$. In the second line, print $k$ integers $a_1, a_2, \ldots, a_k$ — the sequence of length $k$ satisfying the conditions from the problem statement.

If there are several answers, you can print any. It can be proven that at least one valid sequence always exists for any integer $n > 1$.


-----Examples-----

Input
4
2
360
4999999937
4998207083
Output
1
2 
3
2 2 90 
1
4999999937 
1
4998207083


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Number theory

Mathematics

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline
from bisect import bisect_left
from bisect import bisect_right
from math import ceil, factorial

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def nCr(n, k, modulus=1):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
		res %= modulus
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(1000000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
for _ in range(int(input())):
	n = int(input())
	f = primefs(n)
	x = 0
	for i in f:
		x = max(x, f[i])
	a = None
	b = None
	for i in f:
		if f[i] == x and a == None and (x > 1):
			a = i
		elif b == None:
			b = i ** f[i]
		else:
			b *= i ** f[i]
	if not a:
		print(1)
		print(n)
		continue
	ans = [a] * (x - 1)
	if b != None:
		ans.append(b * a)
	else:
		ans.append(a)
	print(x)
	print(*ans)


import math
from collections import Counter, defaultdict, deque

def f(n):
	k = 1
	m = [n]
	for i in range(2, math.floor(math.sqrt(n) + 1)):
		if n % i == 0:
			tempN = n
			tempans = 0
			while tempN % i == 0 and tempN / i % i == 0:
				tempN = tempN // i
				tempans += 1
			if k < tempans + 1:
				k = tempans + 1
				m = [i for j in range(tempans)]
				m.append(tempN)
	return m
t = int(input())
result = []
for i in range(t):
	n = int(input())
	result.append(f(n))
for i in range(t):
	print(len(result[i]))
	for j in range(len(result[i])):
		print(result[i][j], end=' ')
	print()


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def lcm(x, y):
	return x * y / gcd(x, y)

def fact(x, mod=mod):
	ans = 1
	for i in range(1, x + 1):
		ans = ans * i % mod
	return ans

def arr2D(n, m, default=0):
	return [[default for j in range(m)] for i in range(n)]

def arr3D(n, m, r, default=0):
	return [[[default for k in range(r)] for j in range(m)] for i in range(n)]

def sortDictV(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

class DSU:

	def __init__(self, length):
		self.length = length
		self.parent = [-1] * self.length

	def getParent(self, node, start):
		if node >= self.length:
			return False
		if self.parent[node] < 0:
			if start != node:
				self.parent[start] = node
			return node
		return self.getParent(self.parent[node], start)

	def union(self, node1, node2):
		parent1 = self.getParent(node1, node1)
		parent2 = self.getParent(node2, node2)
		if parent1 == parent2:
			return False
		elif self.parent[parent1] <= self.parent[parent2]:
			self.parent[parent1] += self.parent[parent2]
			self.parent[parent2] = parent1
		else:
			self.parent[parent2] += self.parent[parent1]
			self.parent[parent1] = parent2
		return True

	def getCount(self, node):
		return -self.parent[self.getParent(node, node)]

def exact(num):
	if abs(num - round(num)) <= 10 ** (-9):
		return round(num)
	return num
import math

def primeFactors(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n / i
	if n > 2:
		ans.append(n)
	return ans

def solve(n):
	primeDiv = primeFactors(n)
	count = {}
	for i in primeDiv:
		if count.get(i) == None:
			count[i] = 1
		else:
			count[i] += 1
	maxx = 0
	maxxAns = -1
	for i in count:
		if count[i] > maxx:
			maxx = count[i]
			maxxAns = i
	print(maxx)
	mul = 1
	for i in range(maxx - 1):
		print(maxxAns, end=' ')
		mul *= maxxAns
	print(n // mul)
for _ in range(int(input())):
	n = int(input())
	solve(n)


import sys

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

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	n = mint()
	nbak = n
	a = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			c = 0
			while n % i == 0:
				n //= i
				c += 1
			a.append((c, i))
		i += 1
	if n != 1:
		a.append((1, n))
	best = max(a)
	z = best[0]
	print(z)
	if z != 1:
		print(' '.join([str(best[1])] * (z - 1)), end=' ')
	print(nbak // best[1] ** (z - 1))
for i in range(mint()):
	solve()


from collections import defaultdict
import math

def prime(n):
	global d
	while n % 2 == 0:
		d[2] += 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[i] += 1
			n = n // i
	if n > 2:
		d[n] += 1
for _ in range(int(input())):
	n = int(input())
	x = n
	d = defaultdict(int)
	prime(n)
	answer = None
	s = 0
	for (i, j) in d.items():
		if j > s:
			s = j
			answer = (i, j)
	print(answer[1])
	for i in range(answer[1] - 1):
		print(answer[0], end=' ')
		x = x // answer[0]
	if x > 1:
		print(x)
	else:
		print()


t = int(input())
for test in range(t):
	n = int(input())
	primes = dict()
	i = 2
	m = n
	while i * i <= n and m > 1:
		if m % i == 0:
			m = m // i
			primes[i] = primes.get(i, 0) + 1
		else:
			i += 1
	if m > 1:
		primes[m] = primes.get(m, 0) + 1
	exp = [[primes[i], i] for i in primes]
	exp = sorted(exp)[::-1]
	k = exp[0][0]
	result = [1 for i in range(k)]
	for (esponente, primo) in exp:
		for i in range(esponente):
			result[i] *= primo
	result.reverse()
	print(k)
	print(' '.join(map(str, result)))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	copy = n
	while n % 2 == 0:
		d[2] += 1
		n //= 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[i] += 1
			n //= i
	if n > 2:
		d[n] += 1
	extra = 1
	num = 0
	m = 0
	for i in d:
		if d[i] > m:
			m = d[i]
			num = i
	extra = copy // num ** m
	res = [num] * m
	res[-1] *= extra
	print(len(res))
	print(*res)


import math

def primeFactors(n):
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
t = int(input())
for i in range(t):
	l = []
	n = int(input())
	primeFactors(n)
	if len(set(l)) == 1:
		print(len(l))
		print(*l)
		continue
	maks = 0
	for i in set(l):
		if l.count(i) >= maks:
			maks = l.count(i)
			sayi = i
	if maks > 0:
		print(maks)
		last = n // sayi ** (maks - 1)
		print((str(sayi) + ' ') * (maks - 1) + str(last))
	else:
		print(1)
		print(n)


def read():
	return int(input())

def solve(n):
	res = []
	for i in range(2, int(n ** 0.5) + 2):
		if not n % i:
			cur = [0, i]
			while not n % i:
				n //= i
				cur[0] += 1
			res.append(cur)
	if n != 1:
		res.append([1, n])
	return res
for _ in range(read()):
	n = read()
	p = solve(n)
	p.sort(key=lambda x: x[0], reverse=True)
	print(p[0][0])
	for i in range(p[0][0] - 1):
		print(p[0][1], end=' ')
	rem = p[0][1]
	for i in range(1, len(p)):
		for j in range(p[i][0]):
			rem *= p[i][1]
	print(rem)


import sys
import math
import collections
import operator as op
from collections import deque
from math import gcd, inf, sqrt, pi, cos, sin, ceil, log2, floor
from bisect import bisect_right, bisect_left, bisect
from functools import reduce
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(2 ** 20)

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return list(factors)

def isPowerOfTwo(x):
	return x and (not x & x - 1)
MOD = 1000000007
PMOD = 998244353
N = 10 ** 9 + 7
LOGN = 30
alp = 'abcdefghijklmnopqrstuvwxyz'
T = 1
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	a = prime_factors(n)
	if len(a) == 1:
		print(1)
		print(n)
		continue
	d = {}
	for i in a:
		if i not in d:
			d[i] = 0
		d[i] += 1
	isOk = False
	for i in d:
		if d[i] != 1:
			isOk = True
	if not isOk:
		print(1)
		print(n)
		continue
	mx = -1
	val = 0
	for i in d:
		if d[i] >= mx:
			mx = d[i]
			val = i
	print(mx)
	ans = [val] * (mx - 1)
	ans.append(n // val ** (mx - 1))
	print(*ans)


from collections import defaultdict

def primeFactors(n):
	dic = defaultdict(int)
	factors = []
	while n % 2 == 0:
		dic[2] += 1
		n = n // 2
	i = 3
	while i * i <= n:
		while n % i == 0:
			dic[i] += 1
			n = n // i
		i += 2
	if n > 2:
		dic[n] += 1
	return dic

def isPrime(n):
	if n == 1:
		return False
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True

def recur(n, prev, prime):
	if n <= 1:
		return
	i = prime
	flag = 0
	while i * i <= n:
		if n % i == 0 and i % prev == 0:
			flag = 1
			res.append(i)
			break
		i += 1
	if flag:
		recur(n // i, i, prime)
	elif res:
		tmp = res.pop()
		if n % tmp != 0:
			res.append(tmp * n)
		else:
			res.append(tmp)
			res.append(n)
for _ in range(int(input())):
	n = int(input())
	if isPrime(n):
		print(1)
		print(n)
		continue
	factors = primeFactors(n)
	ans = -1
	fin = []
	for prime in factors:
		res = []
		recur(n, 1, prime)
		if len(res) > len(fin):
			fin = res[:]
	print(len(fin))
	print(*fin)


from math import sqrt
from collections import defaultdict

def number_to_sequence(n):
	sqrtn = int(sqrt(n))
	decomposition = defaultdict(int)
	ncp = n
	for i in range(2, sqrtn + 1):
		while n / i % 1 == 0:
			decomposition[i] += 1
			n = n / i
	if n == ncp:
		decomposition[ncp] = 1
	k = max(decomposition.values())
	a = [1 for _ in range(k)]
	for factor in decomposition:
		for power in range(decomposition[factor]):
			a[-(power + 1)] *= factor
	a[-1] *= n
	print(k)
	if k == 1:
		a = [ncp]
	print(' '.join([str(int(i)) for i in a]))
t = int(input())
for _ in range(t):
	n = int(input())
	number_to_sequence(n)


for w in range(int(input())):
	m = n = int(input())
	d = {}
	while m % 2 == 0:
		m //= 2
		d[2] = d.get(2, 0) + 1
	i = 3
	while i * i <= m:
		while m % i == 0:
			m //= i
			d[i] = d.get(i, 0) + 1
		i += 2
	if m:
		d[m] = d.get(m, 0) + 1
	m = 0
	for i in d:
		if d[i] > m:
			m = d[i]
			c = i
	print(m)
	for i in range(m - 1):
		print(c, end=' ')
	print(n // c ** (m - 1))


import sys
import heapq
from collections import deque

def primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def factor(n, l, d):
	F = False
	for p in l:
		if n % p == 0:
			if p in d:
				d[p] += 1
			else:
				d[p] = 1
			F = True
			break
	if F:
		factor(n // p, l, d)

def find(parent, i):
	if parent[i] != i:
		parent[i] = find(parent, parent[i])
	return parent[i]

def union(parent, rank, xx, yy):
	x = find(parent, xx)
	y = find(parent, yy)
	if rank[x] > rank[y]:
		parent[y] = x
	elif rank[y] > rank[x]:
		parent[x] = y
	else:
		parent[y] = x
		rank[x] += 1
ans = 0
n = int(sys.stdin.readline().strip())
for j in range(n):
	s = sys.stdin.readline().strip()
	s = int(s)
	ans = 1
	d = {}
	l = primes(int(s ** 0.5) + 1)
	factor(s, l, d)
	kk = 1
	for k in d:
		if d[k] > ans:
			kk = k
		ans = max(ans, d[k])
	print(ans)
	rl = []
	for i in range(ans - 1):
		rl.append(str(kk))
		s = s // kk
	rl.append(str(s))
	print(' '.join(rl))


import math, sys, heapq, random
from collections import defaultdict, deque, OrderedDict
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

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

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def primeFactors(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n // i
	if n > 2:
		ans.append(n)
	return ans

def main():
	try:
		n = I()
		l = primeFactors(n)
		ma = 0
		ele = 0
		d = {}
		for x in l:
			if d.get(x, -1) != -1:
				d[x] += 1
				if d[x] > ma:
					ma = d[x]
					ele = x
			else:
				d[x] = 1
				if d[x] > ma:
					ma = d[x]
					ele = x
		ans = ma
		an = []
		for i in range(ma - 1):
			an.append(ele)
		an.append(n // ele ** (ma - 1))
		print(len(an))
		print(*an)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(I()):
	main()


from bisect import *
from collections import *
from random import *
from decimal import *
from random import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	pr = {}
	v = n
	while v % 2 == 0:
		v = v // 2
		try:
			pr[2] += 1
		except:
			pr[2] = 1
	for i in range(3, int(n ** 0.5) + 1, 2):
		while v % i == 0:
			v = v // i
			try:
				pr[i] += 1
			except:
				pr[i] = 1
	if v > 2:
		try:
			pr[v] += 1
		except:
			pr[v] = 1
	ma = 0
	p = 0
	for i in pr.keys():
		if pr[i] > ma:
			ma = pr[i]
			p = i
	if ma <= 1:
		print(1)
		print(n)
	else:
		print(ma)
		for i in range(ma - 1):
			print(p, end=' ')
		f = 1
		print(n // p ** (ma - 1))


input = __import__('sys').stdin.readline
import math

def factorize(n):
	count = 0
	res = []
	while not n % 2 > 0:
		n >>= 1
		count += 1
	if count > 0:
		res.append([2, count])
	for i in range(3, int(math.sqrt(n)) + 1):
		count = 0
		while n % i == 0:
			count += 1
			n = int(n / i)
		if count > 0:
			res.append([i, count])
		i += 2
	if n > 2:
		res.append([n, 1])
	return res

def solve(res, n):
	ans = [n]
	for i in res:
		if i[1] > 1:
			ans = max(ans, [i[0]] * (i[1] - 1) + [n // pow(i[0], i[1] - 1)], key=len)
	return ans
for _ in range(int(input())):
	n = int(input())
	res = factorize(n)
	p = solve(res, n)
	print(len(p))
	print(*p)


def factor_with_most_occurrence(n):
	max_occurrence = 1
	mo_factor = n
	m = n
	for i in range(2, int(n ** 0.5) + 1):
		occurrence = 0
		while n % i == 0:
			occurrence += 1
			n //= i
		if max_occurrence < occurrence:
			max_occurrence = occurrence
			mo_factor = i
	return (mo_factor, max_occurrence)

def print_sequence(n, k, mo_factor):
	print(k)
	for _ in range(k - 1):
		n //= mo_factor
		print(mo_factor, end=' ')
	print(n)
t = int(input())
for _ in range(t):
	n = int(input())
	(mo_factor, k) = factor_with_most_occurrence(n)
	print_sequence(n, k, mo_factor)


import sys, math
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	m = int(input())
	A = [m]
	v = math.ceil(math.sqrt(m))
	for i in range(2, v + 1):
		n = m
		B = []
		while n % i == 0:
			v = n // i
			if v % i != 0:
				flag = 1
				B.append(n)
				break
			B.append(i)
			n = n // i
		if len(B) > len(A):
			A = B
	print(len(A))
	print(*A)


t = int(input())
for _ in range(t):
	n = int(input())
	d = {}
	while not n % 2:
		try:
			d[2] += 1
		except:
			d[2] = 1
		n = n // 2
	for i in range(3, int(pow(n, 0.5)) + 1, 2):
		while not n % i:
			try:
				d[i] += 1
			except:
				d[i] = 1
			n = n // i
	if n > 1:
		try:
			d[n] += 1
		except:
			d[n] = 1
	l = []
	for i in d:
		l.append([d[i], i])
	l.sort(reverse=True)
	ans = [l[0][1]] * l[0][0]
	for i in range(1, len(l)):
		for b in range(l[i][0]):
			ans[-1] *= l[i][1]
	print(len(ans))
	print(*ans)


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import *
sys.setrecursionlimit(99999)

def II():
	return int(sys.stdin.buffer.readline().strip())

def IIs():
	return list(map(int, sys.stdin.buffer.readline().strip().split()))
for _ in range(II()):
	n = II()
	n1 = n
	d = collections.defaultdict(int)
	for i in range(2, int(n ** 0.5) + 1):
		if i > n:
			break
		if n % i == 0:
			while n % i == 0:
				d[i] += 1
				n //= i
	if n > 1:
		d[n] += 1
	ans = []
	for (k, v) in d.items():
		if v > len(ans):
			ans = [k] * v
			ans[-1] = n1 // k ** (v - 1)
	print(len(ans))
	print(*ans)


def decompose(number):
	prime_factors = []
	while number % 2 == 0:
		prime_factors.append(2)
		number = number / 2
	for i in range(3, int(number ** (1 / 2)) + 1, 2):
		while number % i == 0:
			prime_factors.append(int(i))
			number = number / i
	if number > 2:
		prime_factors.append(int(number))
	return prime_factors

def check_double(A):
	S = set(A)
	my_dict = {x: A.count(x) for x in S if A.count(x) > 1}
	try:
		return max(my_dict.keys(), key=lambda k: my_dict[k])
	except ValueError:
		return False

def prod(L):
	result = 1
	for x in L:
		result *= x
	return result
for _ in range(int(input())):
	n = int(input())
	prems = decompose(n)
	comp = check_double(prems)
	if comp == False:
		print(1, n, sep='\n')
	else:
		remainder = int(comp * prod([prem for prem in prems if prem != comp]))
		count = prems.count(comp)
		print(count, end='\n')
		for k in range(count - 1):
			print(comp, end=' ')
		print(remainder, end='\n')


for s in [*open(0)][1:]:
	n = m = int(s)
	k = -1
	i = 2
	while i * i <= m:
		j = -1
		while m % i < 1:
			m //= i
			j += 1
		if j > k:
			k = j
			p = i
		i += 1
	if k < 1 < m:
		k = 0
		p = m
	print(k + 1, *[p] * k, n // p ** k)


import math
from collections import Counter

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = int(n / i)
	if n > 2:
		l.append(n)
	return l
for _ in range(int(input())):
	n = int(input())
	tmp = primeFactors(n)
	ans = []
	ind = 0
	d = Counter(tmp)
	z = []
	for i in d:
		z.append([d[i], i])
	z = sorted(z, reverse=True)
	prod = 1
	for i in range(z[0][0] - 1):
		ans.append(z[0][1])
		prod *= z[0][1]
	print(len(ans) + 1)
	print(*ans, int(n / prod))


import math
tc = int(input())
for i in range(tc):
	integer = int(input())
	k = integer
	kamus = dict()
	while k % 2 == 0:
		try:
			kamus[2] += 1
		except:
			kamus[2] = 1
		k /= 2
	for i in range(3, int(math.sqrt(k)) + 1, 2):
		while k % i == 0:
			try:
				kamus[i] += 1
			except:
				kamus[i] = 1
			k /= i
	kamus = sorted(kamus.items(), key=lambda x: x[1], reverse=True)
	if kamus == []:
		print(f'1\n{integer}')
	else:
		(banyak, count) = (kamus[0][0], kamus[0][1])
		last = integer // banyak ** (count - 1)
		print(count)
		print(f'{banyak} ' * (count - 1), end='')
		print(last)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

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

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass
prime = [1 for i in range(10 ** 5 + 10)]
p = []
for i in range(2, 10 ** 5 + 10):
	if prime[i] == 0:
		continue
	p.append(i)
	for j in range(i + i, 10 ** 5 + 10, i):
		prime[j] = 0
prime[0] = prime[1] = 0
for _ in range(L()[0]):
	n = L()[0]
	INITIAL = n
	div = {}
	mx = 0
	final = -1
	for ele in p:
		if n % ele:
			continue
		while n % ele == 0:
			n //= ele
			div[ele] = div.get(ele, 0) + 1
		if div[ele] > mx:
			mx = div[ele]
			final = ele
	if n != 1:
		div[n] = 1
		if mx == 0:
			mx = 1
			final = n
	print(mx)
	print(*[final] * (mx - 1), INITIAL // pow(final, mx - 1))
endtime = time.time()


import math

def primeFactors(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			a.append(i)
			n = n // i
	if n > 2:
		a.append(n)
	return a
a = int(input())
for x in range(a):
	b = int(input())
	s = primeFactors(b)
	if len(s) == 1:
		print(1)
		print(*s)
	else:
		d = {}
		for x in range(len(s)):
			if d.get(s[x]) == None:
				d[s[x]] = 1
			else:
				d[s[x]] += 1
		h = 0
		m = ''
		for x in d:
			if d[x] == h:
				if x > m:
					h = d[x]
					m = x
			elif d[x] > h:
				h = d[x]
				m = x
		l = 1
		for x in range(len(s)):
			if s[x] != m:
				l *= s[x]
		print(h)
		for x in range(h - 1):
			print(m, end=' ')
		print(m * l)


def sieve_eratosthenes(N):
	assert isinstance(N, int), 'sieve_eratosthenes(N): Given N non integer ' + 'data types'
	if N < 2:
		return []
	sieve = list(range(3, N + 1, 2))
	for i in range(3, N + 1, 2):
		if sieve[(i - 3) // 2] is False:
			continue
		for j in range(i * i, N + 1, 2 * i):
			sieve[(j - 3) // 2] = False
	result = [2]
	result.extend(filter(None, sieve))
	return result
primes = sieve_eratosthenes(10 ** 4)
CONST = 10 ** 5

def decompose(N):
	N_before = N
	i = 0
	_ = primes[i]
	__ = len(primes) - 1
	factors = []
	while _ <= N:
		if N % _ == 0:
			count = 0
			while N % _ == 0:
				count += 1
				N //= _
			factors.append([count, _])
		if i < __:
			i += 1
			_ = primes[i]
		else:
			break
	if N > CONST and False:
		factors.append([1, N])
	elif N > primes[-1]:
		i = primes[-1] + 2
		while i * i <= N_before:
			if N % i == 0:
				count = 0
				while N % i == 0:
					count += 1
					N //= i
				factors.append([count, i])
			i += 2
		if N != 1:
			factors.append([1, N])
	return factors
T = int(input())
for tc in range(T):
	N = int(input())
	decomposed = decompose(N)
	decomposed.sort(reverse=True)
	result = []
	multiplier = 1
	for i in range(len(decomposed) - 1):
		multiplier *= decomposed[i][1]
		while decomposed[i][0] > decomposed[i + 1][0]:
			decomposed[i][0] -= 1
			result.append(multiplier)
	multiplier *= decomposed[-1][1]
	for i in range(decomposed[-1][0]):
		result.append(multiplier)
	print(len(result))
	print(' '.join(map(str, result)))


def prime_factorize(n):
	pf = {}
	orig_n = n
	p = 2
	while n > 1 and p * p <= orig_n:
		if n % p == 0:
			pf[p] = 0
			while n % p == 0:
				pf[p] += 1
				n //= p
		p += 1
	if n > 1:
		pf[n] = 1
	return pf
for _ in range(int(input())):
	n = int(input())
	pf = prime_factorize(n)
	ans = [1 for i in range(max(pf.values()))]
	for (p, e) in pf.items():
		for i in range(e):
			ans[i] *= p
	ans.reverse()
	print(len(ans))
	print(*ans)


def is_prime(n):
	if n == 2:
		return True
	if n % 2 == 0:
		return False
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			return False
	return True

def break_it(n, i):
	(c, t) = (0, n)
	while t % i == 0:
		c += 1
		t = t // i
	c -= 1
	t = t * i
	return [c, t]

def solve():
	n = int(input())
	(k, ans, ak) = (0, 0, 0)
	if is_prime(n):
		print(1)
		print(n)
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				res = break_it(n, i)
				if res[0] > k:
					k = res[0]
					ans = i
					ak = res[1]
		if k != 0:
			print(k + 1)
			for i in range(k):
				print(ans, end=' ')
			print(ak)
		else:
			print(1)
			print(n)
for _ in range(int(input())):
	solve()


def prime_factorize(n):
	pf = {}
	orig_n = n
	p = 2
	while n > 1 and p * p <= orig_n:
		if n % p == 0:
			pf[p] = 0
			while n % p == 0:
				pf[p] += 1
				n //= p
		p += 1
	if n > 1:
		pf[n] = 1
	return pf
for _ in range(int(input())):
	n = int(input())
	pf = prime_factorize(n)
	mx = 0
	theRepeater = 0
	for (ky, val) in pf.items():
		if val > mx:
			mx = val
			theRepeater = ky
	ans = [theRepeater] * mx
	for (ky, val) in pf.items():
		if ky == theRepeater:
			pass
		else:
			for i in range(val):
				ans[-1] *= ky
	print(mx)
	print(*ans)


import math

def p(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	return l
for _ in range(int(input())):
	n = int(input())
	res = p(n)
	c = max(set(res), key=res.count)
	print(res.count(c))
	m = []
	pr = 1
	for i in range(res.count(c) - 1):
		m.append(c)
		pr *= c
	m.append(n // pr)
	print(*m, sep=' ')


import sys
from collections import defaultdict as dc
from collections import Counter
from bisect import bisect_right, bisect_left
import math
from operator import itemgetter
from heapq import heapify, heappop, heappush
for _ in range(int(input())):
	n = int(input())
	l = []
	m = 1
	l = [n]
	i = 2
	while i <= int(math.sqrt(n)) + 1:
		p = n
		c = 0
		while p % i == 0:
			c += 1
			p = p // i
		if c > m:
			m = c
			l = [i] * (c - 1) + [p * i]
		i += 1
	print(m)
	print(*l)


import math
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	n1 = n
	d = defaultdict(int)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[i] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	x = list(d.values())
	y = list(d.keys())
	maxi = max(x)
	for i in range(len(x)):
		if d[y[i]] == maxi:
			ans = y[i]
			break
	c = []
	for i in range(maxi - 1):
		c.append(ans)
	c.append(n1 // ans ** (maxi - 1))
	print(len(c))
	print(*c)


import os
import sys
from io import BytesIO, IOBase
import math

def prime_factorize(n):
	n2 = n
	i = 2
	ans = []
	while n > 1:
		if i > math.sqrt(n2):
			if len(ans) == 0:
				return [(n2, 1)]
			else:
				ans.append((n, 1))
				return ans
		power = 0
		while n % i == 0:
			power += 1
			n = n // i
		if power >= 1:
			ans.append((i, power))
		i += 1
	return ans

def main():
	for _ in range(ii()):
		n = ii()
		a = prime_factorize(n)
		maxpow = max([j[1] for j in a])
		print(maxpow)
		for j in range(maxpow):
			b = 1
			for i in range(len(a)):
				(prime, power) = a[i]
				if power >= maxpow - j:
					b *= prime
			print(b)

def mpin():
	return map(int, input().split())

def lmpin():
	return list(mpin())

def ii():
	return int(input())

def gridi(h, w):
	return [lmpin() for i in range(h)]

def gridstr(h, w):
	return [list(input()) for i in range(h)]

def zero1(h):
	return [0 for i in range(h)]

def zero2(h, w):
	return [[0 for j in range(w)] for i in range(h)]
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n,) = I()
	pf = []
	ct = 0
	cp = n
	while n % 2 == 0:
		n //= 2
		ct += 1
	if ct:
		pf.append([2, ct])
	for i in range(3, int(n ** 0.5) + 1, 2):
		ct = 0
		while n % i == 0:
			n //= i
			ct += 1
		if ct:
			pf.append([i, ct])
	if n > 1:
		pf.append([n, 1])
	(a, b) = max(pf, key=lambda x: x[1])
	an = [a] * b
	an[-1] *= cp // pow(a, b)
	print(len(an))
	print(*an)


t = int(input())
from collections import Counter
simple = [2, 3]
for _ in range(t):
	n = int(input())
	d = Counter()
	i = 0
	while n > 1 and i < len(simple):
		while n % simple[i] == 0:
			d[simple[i]] += 1
			n //= simple[i]
		i += 1
	i = simple[-1] + 2
	while n > 1 and i ** 2 <= n:
		while n % i == 0:
			d[i] += 1
			n //= i
		i += 2
	if n > 1 and i ** 2 > n:
		d[n] += 1
	m = max(d.values())
	print(m)
	while m > 0:
		r = 1
		for el in d:
			if d[el] >= m:
				r *= el
				d[el] -= 1
		m -= 1
		print(r, end=' ')
	print()


from collections import *
from math import *

def PrimeFactors(n):
	factors = []
	if n < 0:
		factors.append(-1)
		n = abs(n)
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 1:
		factors.append(n)
	return factors
for i1 in range(int(input())):
	n = int(input())
	fact = PrimeFactors(n)
	C = Counter(fact)
	C = [(C[i], i) for i in C]
	C.sort(reverse=True)
	ans = [C[0][1]] * C[0][0]
	for (f, x) in C[1:]:
		ans[-1] *= x ** f
	print(len(ans))
	print(*ans)


from sys import stdin, stdout
import heapq as hq
from collections import defaultdict
from math import sqrt
t = int(input())
for tc in range(t):
	n = int(stdin.readline())
	no = n
	d = 2
	f = []
	while d <= sqrt(n):
		if n % d == 0:
			f.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		f.append(n)
	last = -1
	kmax = -1
	cmax = 0
	c = 0
	for v in f:
		if v == last:
			c += 1
		else:
			if c > cmax:
				cmax = c
				kmax = last
			last = v
			c = 1
	if c > cmax:
		cmax = c
		kmax = last
	if cmax == 1:
		res_n = 1
		res_ar = [no]
	else:
		res_n = cmax
		res_ar = (cmax - 1) * [kmax] + [no // kmax ** (cmax - 1)]
	res_ari = [str(x) for x in res_ar]
	stdout.write(str(res_n) + '\n')
	stdout.write(str(' '.join(res_ari)) + '\n')


import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
	n = int(input())
	i = 2
	prev = 1
	ls = []
	answer = []
	for i in range(2, n):
		if i * i > n:
			break
		cnt = 0
		while n % i == 0:
			cnt += 1
			n //= i
		if cnt != 0:
			ls.append([cnt, i])
	if n != 1:
		ls.append([1, n])
	tmp = 1
	flag = True
	ls = sorted(ls, reverse=True)
	for (i, j) in ls:
		if flag:
			for _ in range(i - 1):
				answer.append(j)
			tmp *= j
			flag = False
		else:
			for k in range(i):
				tmp *= j
	if tmp != 1:
		answer.append(tmp)
	print(len(answer))
	for i in range(len(answer)):
		print(answer[i], end=' ')
	print()


from math import gcd
from bisect import bisect_left, bisect_right
from itertools import combinations
from itertools import permutations
from bisect import bisect_left
from math import ceil
from math import radians
from heapq import heapify, heappush, heappop, nsmallest
import bisect
from math import pi
from collections import deque
from math import factorial
from math import log, ceil
from collections import defaultdict
from math import *
from sys import stdin, stdout
import itertools
import os
import sys
import threading
from collections import deque, Counter, OrderedDict, defaultdict
from heapq import *
from fractions import Fraction
mod = int(pow(10, 9) + 7)

def ii():
	return int(input())

def si():
	return str(input())

def mi():
	return map(int, input().split())

def li1():
	return list(mi())

def fii():
	return int(stdin.readline())

def fsi():
	return str(stdin.readline())

def fmi():
	return map(int, stdin.readline().split())

def fli():
	return list(fmi())
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d:
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d:
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = defaultdict(list)
	for i in range(n):
		(x, y) = mi()
		d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans

def primeFactors(n):
	s = set()
	while n % 2 == 0:
		s.add(2)
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0 and i % 2 == 1:
			s.add(i)
			n = n // i
	if n > 2 and n % 2 == 1:
		s.add(n)
	return s

def find_all(a_str, sub):
	start = 0
	while True:
		start = a_str.find(sub, start)
		if start == -1:
			return
		yield start
		start += len(sub)

def SieveOfEratosthenes(n, isPrime):
	isPrime[0] = isPrime[1] = False
	for i in range(2, n):
		isPrime[i] = True
	p = 2
	while p * p <= n:
		if isPrime[p] == True:
			i = p * p
			while i <= n:
				isPrime[i] = False
				i += p
		p += 1
	return isPrime

def dijkstra(edges, f, t):
	g = defaultdict(list)
	for (l, r, c) in edges:
		g[l].append((c, r))
	(q, seen, mins) = ([(0, f, ())], set(), {f: 0})
	while q:
		(cost, v1, path) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			path = (v1, path)
			if v1 == t:
				return (cost, path)
			for (c, v2) in g.get(v1, ()):
				if v2 in seen:
					continue
				prev = mins.get(v2, None)
				next = cost + c
				if prev is None or next < prev:
					mins[v2] = next
					heappush(q, (next, v2, path))
	return float('inf')

def binsearch(a, l, r, x):
	while l <= r:
		mid = l + (r - 1) // 2
		if a[mid]:
			return mid
		elif a[mid] > x:
			l = mid - 1
		else:
			r = mid + 1
	return -1

def readTree(n):
	adj = [set() for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].add(v - 1)
		adj[v - 1].add(u - 1)
	return adj

def treeOrderByDepth(n, adj, root=0):
	parent = [-2] + [-1] * (n - 1)
	ordered = []
	q = deque()
	q.append(root)
	depth = [0] * n
	while q:
		c = q.popleft()
		ordered.append(c)
		for a in adj[c]:
			if parent[a] == -1:
				parent[a] = c
				depth[a] = depth[c] + 1
				q.append(a)
	return (ordered, parent, depth)

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def nextPowerOf2(n):
	count = 0
	if n and (not n & n - 1):
		return n
	while n != 0:
		n >>= 1
		count += 1
	return 1 << count

def cou(n):
	c = 0
	while n > 1:
		c += 1
		n //= 2
	return c

def sortsec(l):
	return sorted(l, key=lambda x: x[1])

def BinarySearch(a, x):
	i = bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def subarray(A):
	r = set()
	p = {0}
	for x in A:
		p = {x | y for y in p} | {x}
		r |= p
	return len(r)

def setBitNumber(n):
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n = n + 1
	return n >> 1

def countSetBits(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count

def allsub(l):
	n = len(l)
	a = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			a.append(l[i:j])
	return a
for _ in range(ii()):
	n = ii()
	p = sorted(list(primeFactors(n)))
	ans = []
	x = n
	i = 0
	while n > 1:
		if i < len(p) and n % p[i] == 0:
			ans.append(p[i])
			n = n // p[i]
		else:
			i += 1
	d = defaultdict(int)
	for i in ans:
		d[i] += 1
	m = 0
	n = 0
	for i in d.keys():
		if d[i] > m:
			m = d[i]
			n = i
	mul = 1
	ans1 = []
	for i in range(m - 1):
		ans1.append(n)
		mul *= n
	ans1.append(x // mul)
	print(len(ans1))
	print(*ans1)


N = 10 ** 5
primes = [2]
isPrime = [True] * N
for i in range(3, N, 2):
	if isPrime[i]:
		primes.append(i)
		for j in range(i * i, N, i + i):
			isPrime[j] = False
from collections import defaultdict

def factorize(n):
	ans = defaultdict(lambda : 1)
	for p in primes:
		if p > n:
			break
		m = 0
		while n % p == 0:
			n //= p
			ans[m] *= p
			m += 1
	if n > 1:
		ans[0] *= n
	return ans
for _ in range(int(input())):
	n = int(input())
	ans = factorize(n)
	print(len(ans))
	print(' '.join(map(str, (ans[i] for i in range(len(ans) - 1, -1, -1)))))


import math
for _ in range(int(input())):
	n = int(input())
	x = n
	high = 0
	temp = 0
	num = 0
	while n % 2 == 0:
		temp += 1
		n = n / 2
	if temp > high:
		high = temp
		num = 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		temp = 0
		while n % i == 0:
			temp += 1
			n = n / i
		if temp > high:
			high = temp
			num = i
	if high == 0:
		high = 1
		num = x
	print(high)
	for i in range(high - 1):
		print(num, end=' ')
	print(x // num ** (high - 1))


def calculate(n):
	maxC = 1
	maxI = n
	backupN = n
	for i in range(2, int(n ** 0.5) + 1):
		c = 0
		while n % i == 0:
			c = c + 1
			n //= i
		if maxC < c:
			maxC = c
			maxI = i
	print(maxC)
	n = backupN
	for _ in range(0, maxC - 1):
		n //= maxI
		print(maxI, end=' ')
	print(n)
numberOfTestCases = int(input())
for _ in range(numberOfTestCases):
	n = int(input())
	calculate(n)


from math import *
dem = [0] * 100007
for _ in range(int(input())):
	n = int(input())
	ok = 0
	for x in range(2, int(sqrt(n)) + 2):
		if n % x == 0:
			ok = 1
	if ok == 0:
		print(1)
		print(n)
		continue
	ans = 0
	ansx = 0
	m = n
	for x in range(2, int(sqrt(n)) + 2):
		dem[x] = 0
		while n > 1 and n % x == 0:
			n //= x
			dem[x] += 1
		if ans < dem[x]:
			ans = dem[x]
			ansx = x
		if n == 1:
			break
	if n > 1:
		dem[x] = 1
	if ans == 1:
		print(1)
		print(m)
	else:
		print(ans)
		for x in range(ans - 1):
			print(ansx, end=' ')
		print(m // ansx ** (ans - 1))


from functools import reduce
for _ in range(int(input())):
	n = int(input())
	nn = n
	ps = {}
	for i in range(2, int(n ** 0.5) + 1):
		if nn % i == 0:
			ps[i] = 0
			while nn % i == 0:
				nn //= i
				ps[i] += 1
	if nn > 1:
		ps[nn] = ps.get(nn, 0) + 1
	l = max(ps.keys(), key=ps.get)
	a = [l] * (ps[l] - 1)
	a.append(n // reduce(int.__mul__, a, 1))
	print(len(a))
	print(*a)


import math

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors

def product(lst):
	p = 1
	for i in lst:
		p *= i
	return p
t = int(input())
for tc in range(t):
	n = int(input())
	primefactorization = primeFactors(n)
	mode = max(set(primefactorization), key=primefactorization.count)
	modeocc = primefactorization.count(mode)
	arrfin = []
	modediv = 1
	for x in range(modeocc - 1):
		arrfin.append(mode)
		modediv *= mode
	arrfin.append(product(primefactorization) // modediv)
	print(len(arrfin))
	print(' '.join([str(i) for i in arrfin]))


import math
from collections import Counter

def primeFactors(n):
	res = []
	while n % 2 == 0:
		res.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			res.append(i)
			n = n / i
	if n > 2:
		res.append(int(n))
	return res

def solution(item):
	primes = primeFactors(item)
	if len(primes) == 1:
		print(1)
		print(*primes)
		return
	cnt = Counter(primes)
	cnts = cnt.most_common()
	if len(cnt) == 1:
		print(cnts[0][1])
		print(*[cnts[0][0]] * cnts[0][1])
		return
	t = [cnts[0][0] for i in range(cnts[0][1] - 1)]
	res = cnts[0][0]
	for item in primes:
		if item != cnts[0][0]:
			res = res * item
	t.append(res)
	print(len(t))
	print(*t)
t = int(input())
for _ in range(t):
	z = int(input())
	solution(z)


from math import sqrt

def prime(n):
	X = []
	while n % 2 == 0:
		X.append(2)
		n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			X.append(i)
			n = n / i
	if n > 2:
		X.append(n)
	return X
t = int(input())
for _ in range(t):
	m = int(input())
	X = prime(m)
	ANS = []
	D = dict()
	for _ in X:
		if _ in D:
			D[_] += 1
		else:
			D[_] = 1
	D = {k: v for (k, v) in sorted(D.items(), reverse=True, key=lambda item: item[1])}
	L = list(D.keys())
	ANS = []
	for _ in range(len(L)):
		if _ == 0:
			ANS += [L[_]] * (D[L[_]] - 1)
			x = L[_]
		else:
			x *= L[_] ** D[L[_]]
	ANS.append(int(x))
	print(len(ANS))
	print(*ANS)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	c = n
	b = []
	i = 2
	cnt = 0
	mx = 1
	k = 1
	while c != 1 and i <= int(n ** 0.5):
		if c % i == 0:
			b.append(i)
			c = c // i
			cnt += 1
		else:
			i += 1
			cnt = 0
		if cnt > mx:
			mx = cnt
			k = i
	if c != 1:
		b.append(c)
	S = 1
	c = []
	for i in range(len(b)):
		if b[i] == k:
			c.append(k)
		else:
			S = S * b[i]
	S = S * k
	c = c[1:] + [S]
	print(len(c))
	print(*c)


def splitt(n):
	res = []
	elements = -1
	while n > 1:
		i = 2
		c = 2
		k = 0
		while n >= i ** 2:
			if n % i != 0:
				c = 2
				i += 1
				continue
			while c < i:
				if i % c == 0:
					break
				c += 1
			if c == i:
				k = i
				res += [[i, 1]]
				elements += 1
				n //= i
				while n % i == 0:
					res[elements][1] += 1
					n //= i
			c = 2
			i += 1
		if k == 0:
			i = n
			res += [[i, 1]]
			elements += 1
			break
	return res
t = int(input())
for i in range(t):
	n = int(input())
	res = splitt(n)
	maxi = 0
	maxi_p = 0
	for j in range(len(res)):
		if res[j][1] > maxi_p:
			maxi = res[j][0]
			maxi_p = res[j][1]
	ans = [maxi]
	for j in range(len(res)):
		if res[j][0] != maxi:
			ans[0] *= res[j][0] ** res[j][1]
	ans += [maxi] * (maxi_p - 1)
	print(len(ans))
	print(' '.join(map(str, sorted(ans))))


T = int(input())
for _ in range(T):
	N = int(input())
	num = 1
	ans = 2
	for i in range(2, int(N ** (1 / 2) + 1)):
		if N % i == 0:
			c = 0
			a = N
			while a % i == 0 and a > 0:
				c += 1
				a //= i
			if c > num:
				num = c
				ans = i
	print(num)
	num -= 1
	while num:
		print(ans, end=' ')
		N //= ans
		num -= 1
	print(N)


import sys
from math import gcd, ceil
INF = float('inf')
MOD = 998244353
mod = 10 ** 9 + 7
from collections import Counter, defaultdict as df
from functools import reduce
from math import gcd, ceil, floor, sqrt, copysign, factorial, fmod, fsum, degrees

def li():
	return list(map(int, sys.stdin.readline().strip().split()))

def ini():
	return int(sys.stdin.readline())

def inp():
	return map(int, sys.stdin.readline().strip().split())

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

def inputm(n, m):
	return [li() for i in range(m)]

def so(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

def p(n):
	d = df(lambda : 0)
	l = []
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			d[i] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d
for i in range(ini()):
	n = ini()
	d = p(n)
	m = max(list(d.values()))
	for (i, j) in d.items():
		if j == m:
			c = i
			break
	d = so(d)
	l = [1 for i in range(m)]
	for (i, j) in d.items():
		for k in range(j):
			l[k] *= i
	print(m)
	for i in range(m - 1, -1, -1):
		print(l[i], end=' ')
	print()


import math
from collections import defaultdict

def primeFactors(n):
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
for i in range(int(input())):
	n = int(input())
	l = []
	primeFactors(n)
	d = defaultdict(int)
	for i in l:
		d[i] += 1
	value = 0
	for i in d:
		if d[i] > value:
			key = i
			value = d[i]
	if value == 1:
		print(1)
		print(n)
	else:
		prod = 1
		for i in l:
			if i != key:
				prod *= i
		prod *= key
		ans = []
		for i in range(value - 1):
			ans.append(key)
		ans.append(int(prod))
		print(len(ans))
		print(*ans)


from collections import Counter
from math import sqrt

def prime_factor(n: int) -> list:
	out = []
	i = 2
	while i < int(sqrt(n)) + 1:
		if n % i == 0:
			out.append(i)
			n //= i
		else:
			i += 1
	out.append(n)
	return out
t: int = int(input())
for _ in range(t):
	n = int(input())
	primeFactors = prime_factor(n)
	freq_table = Counter(primeFactors)
	freq_list = sorted(freq_table.items(), key=lambda x: -x[1])
	num = freq_list[0][0]
	freq = freq_list[0][1]
	out = [str(num)] * (freq - 1)
	out.append(str(n // num ** (freq - 1)))
	print(freq)
	print(' '.join(out))


import math

def judge(num):
	if num == 1:
		numlist.append(1)
		numnum.append(1)
		return 0
	for i in range(2, int(math.sqrt(num)) + 3):
		time = 0
		while num % i == 0:
			time += 1
			num = num // i
		if time == 0:
			pass
		else:
			numlist.append(i)
			numnum.append(time)
		if num < i:
			break
	if num != 1:
		numlist.append(num)
		numnum.append(1)
t = int(input())
for i in range(t):
	numlist = []
	numnum = []
	n = int(input())
	judge(n)
	res = []
	for k in range(max(numnum)):
		res.append(1)
	for k in range(len(numlist)):
		for h in range(numnum[k]):
			res[h] *= numlist[k]
	res.reverse()
	print(max(numnum))
	for m in res:
		print(m, end=' ')
	print('')


import math

def primeFactors(n):
	l = []
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	if c > 0:
		l.append([c, 2])
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		c = 0
		while n % i == 0:
			c += 1
			n = n // i
		if c > 0:
			l.append([c, i])
	if n > 2:
		l.append([1, n])
	l.sort()
	(maxc, maxf) = l.pop()
	cur = 1
	for pair in l:
		cur *= pair[1] ** pair[0]
	maxc -= 1
	cur *= maxf
	print(maxc + 1)
	for i in range(maxc):
		print(maxf, end=' ')
	print(cur)
for _ in range(int(input())):
	n = int(input())
	primeFactors(n)


for _ in range(int(input())):
	n = int(input())
	MAX = 1
	p = n
	m = n
	for i in range(2, int(n ** 0.5) + 1):
		vp = 0
		while n % i == 0:
			vp += 1
			n //= i
		if vp > MAX:
			MAX = vp
			p = i
	print(MAX)
	for i in range(MAX - 1):
		m //= p
		print(p, end=' ')
	print(m)


from collections import *
from heapq import *
from itertools import *
from functools import *
from random import *
import sys
INF = float('Inf')

def genTokens(lines):
	for line in lines:
		for token in line.split():
			yield token

def nextFn(fn):
	return lambda it: fn(it.__next__())
nint = nextFn(int)

def genCases():
	it = genTokens(sys.stdin)
	T = nint(it)
	for _ in range(T):
		N = nint(it)
		yield N
primes = [True for _ in range(100001)]
primeSet = set()
primesSorted = []

def sieve():
	global primes
	global primeSet
	global primesSorted
	primes[0] = False
	primes[1] = False
	for p in range(2, 100001):
		if not primes[p]:
			continue
		primeSet.add(p)
		cursor = 2 * p
		while cursor < 100001:
			primes[cursor] = False
			cursor += p
	primesSorted = sorted(primeSet)

def main():
	sieve()
	for case in genCases():
		solve(case)

def solve(N):
	factors = []
	remain = N
	for p in primesSorted:
		ct = 0
		while remain % p == 0:
			remain = remain // p
			ct += 1
		if ct > 0:
			factors.append((p, ct))
	if remain > 1:
		factors.append((remain, 1))
	maxCardFactor = max(factors, key=lambda f: f[1])
	product = []
	remainCard = maxCardFactor[1]
	remain = N
	while remainCard > 1:
		product.append(maxCardFactor[0])
		remainCard -= 1
		remain = remain // maxCardFactor[0]
	product.append(remain)
	print(len(product))
	print(*product)
main()


def f(n):
	a = n
	b = dict()
	c = 1
	while c < a ** 0.5 + 1:
		c += 1
		if a % c == 0:
			b[c] = 0
			while a % c == 0:
				b[c] += 1
				a //= c
	if a != 1:
		b[a] = 1
	return b

def g(m, n):
	a = 0
	b = 0
	for i in n:
		b = i * (n[i] > a) + b * (not n[i] > a)
		a = max(a, n[i])
	c = []
	for i in range(a - 1):
		c.append(b)
	c.append(m // b ** (a - 1))
	return c
for testcase in range(int(input())):
	a = int(input())
	b = g(a, f(a))
	print(len(b))
	print(' '.join(list(map(str, b))))


from math import *
from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	div = {}
	sq = int(sqrt(n))
	i = 2
	while i <= sq and n > 1:
		if n % i == 0:
			div[i] = div.get(i, 0) + 1
			n = n // i
			i = 2
			sq = int(sqrt(n))
		else:
			i += 1
	if n > 1:
		div[n] = div.get(n, 0) + 1
	tp = []
	for (key, value) in div.items():
		tp.append((value, key))
	tp.sort(key=lambda x: -1 * x[0])
	div = []
	for (value, key) in tp:
		for index in range(value):
			div.append(key)
	ans = []
	v = div[0]
	w = len(div)
	index = 1
	while index < w:
		if div[index] % v == 0:
			ans.append(v)
			v = div[index]
		else:
			v = v * div[index]
		index += 1
	ans.append(v)
	stdout.write(str(len(ans)) + '\n')
	for v in ans:
		stdout.write(str(v) + ' ')
	stdout.write('\n')


import sys
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())
N = 1000001
ok = [1] * N
primes = []
for i in range(2, N):
	if ok[i]:
		primes.append(i)
		for j in range(i + i, N, i):
			ok[j] = 0
for _ in range(II()):
	n = II()
	nn = n
	(num, mx) = (0, 0)
	for p in primes:
		cnt = 0
		while n % p == 0:
			n //= p
			cnt += 1
		if cnt > mx:
			mx = cnt
			num = p
	if n > 1:
		if mx < 1:
			mx = 1
			num = p
	print(mx)
	print(*[num] * (mx - 1), nn // num ** (mx - 1))


import sys
import math
import collections

def primeFactors(n):
	l = []
	if n % 2 == 0:
		l.append(2)
	while n % 2 == 0:
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			l.append(i)
		while n % i == 0:
			n = n / i
	if n > 2:
		l.append(n)
	return l
t = int(input())
for w in range(t):
	n = int(input())
	l = primeFactors(n)
	l1 = []
	m = 0
	c1 = 0
	for i in l:
		n1 = n
		c = 0
		l2 = []
		if n1 // i % i == 0:
			c1 = 1
			while n1 // i % i == 0:
				c += 1
				l2.append(i)
				n1 //= i
			c += 1
			l2.append(n1)
		if c > m:
			m = c
			l1 = []
			for i in range(len(l2)):
				l1.append(l2[i])
	if c1 == 0:
		print(1)
		print(n)
	else:
		print(m)
		print(*l1)


for _ in range(int(input())):
	n = int(input())
	a = []
	ind = 2
	while n > 1:
		if ind * ind > n:
			a.append(n)
			break
		while n % ind == 0:
			n //= ind
			a.append(ind)
		ind += 1
	d = {}
	k = 0
	for i in a:
		d[i] = d.get(i, 0) + 1
		k = max(k, d[i])
	ans = k
	d = dict(sorted(d.items(), key=lambda item: item[1]))
	b = list(d.keys())
	l = len(b)
	print(k)
	li = []
	for i in range(k):
		ans = 1
		for j in range(l):
			if d[b[-j - 1]] == 0:
				break
			ans *= b[-j - 1]
			d[b[-j - 1]] -= 1
		li.append(ans)
	print(*li[::-1])


import math

def primeFactors(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			(a.append(i),)
			n = n / i
	if n > 2:
		a.append(n)
	return a
t = int(input())
for i in range(t):
	n = int(input())
	d = {}
	a1 = primeFactors(n)
	for j in a1:
		if j not in d:
			d[j] = 1
		else:
			d[j] += 1
	j1 = sorted(d.items(), key=lambda kv: (kv[1], kv[0]))
	k1 = j1[-1][0]
	v1 = j1[-1][1]
	print(v1)
	for j in range(v1 - 1):
		print(int(k1), end=' ')
	print(int(n // k1 ** (v1 - 1)))


import math
global prime
prime = [True for i in range(10 ** 5 + 1)]

def SieveOfEratosthenes(n):
	n2 = int(n)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, int(math.sqrt(n)) + 10, p):
				prime[i] = False
		p += 1

def solve(n):
	freq_max = 0
	max_dig = 0
	max_prod = 0
	i = 2
	n2 = int(n)
	while i * i <= n2:
		if prime[i]:
			n = int(n2)
			if n % i == 0:
				freq = 0
				prod = 1
				while n % i == 0:
					prod *= i
					freq += 1
					n /= i
				if freq > freq_max:
					freq_max = freq
					max_dig = i
					if n == 1:
						break
		i += 1
	if max_dig == 0:
		print(1)
		print(n2)
	elif freq_max == 1:
		if n2 // max_dig % max_dig == 0:
			print(2)
			print(max_dig, n2 // max_dig)
		else:
			print(1)
			print(n2)
	else:
		z = int(freq_max)
		print(z)
		while freq_max != 1:
			print(max_dig, end=' ')
			freq_max -= 1
		print(n2 // max_dig ** (z - 1))
T = int(input())
SieveOfEratosthenes(10 ** 5 + 1)
for i in range(T):
	global n
	n = int(input())
	solve(n)


import os
import sys
from io import BytesIO, IOBase
import math

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n
for xyz in range(0, int(input())):
	n = int(input())
	r = int(n ** 0.5) + 1
	fa = []
	for i in range(2, r):
		if n % i == 0:
			fa.append(i)
	maxf = fac = 0
	for i in fa:
		t = n
		cc = 0
		while t % i == 0:
			t //= i
			cc += 1
		if cc > maxf:
			maxf = cc
			fac = i
	if maxf <= 1:
		print(1)
		print(n)
	else:
		print(maxf)
		p = 1
		for i in range(0, maxf - 1):
			print(fac, end=' ')
			p *= fac
		print(n // p)


from collections import Counter

def nint():
	return int(input())

def nintA():
	return [int(x) for x in input().split()]

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors

def f():
	n = nint()
	l = prime_factors(n)
	c = Counter(l)
	m = max(c.values())
	print(m)
	r = [1] * m
	for (k, v) in c.items():
		for j in range(v):
			r[-1 - j] *= k
	print(*r)
t = int(input())
for i in range(t):
	f()


import math

def _sieve(N):
	primes = [True] * (N + 1)
	primes[0] = False
	primes[1] = False
	sqrtN = round(math.sqrt(N))
	for i in range(2, sqrtN + 1):
		if primes[i]:
			for j in range(i * i, N + 1, i):
				primes[j] = False
	return primes

def _getPrime(N):
	primes = _sieve(N)
	result = []
	for i in range(len(primes)):
		if primes[i]:
			result.append(i)
	return result

def _primeFactor(N):
	primes = _getPrime(round(math.sqrt(N)) + 1)
	count = 0
	primeFactorRes = []
	for prime in primes:
		if N % prime == 0:
			count += 1
			primeFactorRes.append([prime, 0])
		while N % prime == 0:
			N = N // prime
			primeFactorRes[-1][1] += 1
	return primeFactorRes

def Solution(n):
	factors = sorted(_primeFactor(n), key=lambda x: -x[1])
	res = []
	if len(factors) > 0:
		for _ in range(factors[0][1]):
			res.append(factors[0][0])
		res[-1] *= n // pow(factors[0][0], factors[0][1])
		print(len(res))
		for f in res:
			print(f, end=' ')
		print('')
	else:
		print(1)
		print(n)
for t in range(int(input())):
	N = int(input())
	Solution(N)


import math
import sys
input = iter(sys.stdin.read().splitlines()).__next__

def solve(n):
	orig_n = n
	factors = []
	pow_2 = 0
	while 1 ^ n & 1:
		pow_2 += 1
		n >>= 1
	if pow_2:
		factors.append((pow_2, 2))
	max_factor = int(math.sqrt(n))
	for i in range(3, max_factor + 1, 2):
		pow_i = 0
		while n % i == 0:
			pow_i += 1
			n //= i
		if pow_i:
			factors.append((pow_i, i))
	if factors:
		(length, prime) = max(factors)
		seq = [prime] * length
		seq[-1] = orig_n // prime ** (length - 1)
		return [length, ' '.join(map(str, seq))]
	return [1, n]
t = int(input())
output = []
for _ in range(t):
	n = int(input())
	output.extend(solve(n))
print(*output, sep='\n')


import math

def primeFactors(n):
	d = {}
	while n % 2 == 0:
		if d.get(2):
			d[2] += 1
		else:
			d[2] = 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if d.get(i):
				d[i] += 1
			else:
				d[i] = 1
			n = n / i
	if n > 2:
		if d.get(n):
			d[n] += 1
		else:
			d[n] = 1
	return d
for _ in range(int(input())):
	n = int(input())
	t = n
	d = primeFactors(t)
	m = -1
	z = 1
	for i in d:
		m = max(m, d[i])
		if m == d[i]:
			z = i
	print(m)
	for i in range(m - 1):
		print(z, end=' ')
	print(int(n // z ** (m - 1)))


import sys
input = sys.stdin.readline
import math

def fact(x):
	L = int(math.sqrt(x))
	FACT = dict()
	for i in range(2, L + 2):
		while x % i == 0:
			FACT[i] = FACT.get(i, 0) + 1
			x = x // i
	if x != 1:
		FACT[x] = FACT.get(x, 0) + 1
	return FACT
t = int(input())
for tests in range(t):
	n = int(input())
	F = fact(n)
	ANS = 1
	ANSLIST = [n]
	for f in F:
		if F[f] == 1:
			continue
		for i in range(ANS, F[f]):
			if n // f ** i >= f:
				ANSLIST = [f] * i + [n // f ** i]
		ANS = len(ANSLIST)
	print(ANS)
	print(*ANSLIST)


import bisect
import collections
import functools
import itertools
import math
import heapq
import random
import string

def repeat(_func=None, *, times=1):

	def decorator(func):

		@functools.wraps(func)
		def wrapper(*args, **kwargs):
			for _ in range(times):
				func(*args, **kwargs)
		return wrapper
	if _func is None:
		return decorator
	else:
		return decorator(_func)

def unpack(func=int):
	return map(func, input().split())

def l_unpack(func=int):
	return list(map(func, input().split()))

def s_unpack(func=int, rev=False):
	return sorted(map(func, input().split()), reverse=rev)

def ml_unpack(n):
	return [int(input()) for _ in range(n)]

def range_n():
	return range(int(input()))

def getint():
	return int(input())

def getmatrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def display_matrix(mat):
	for i in range(len(mat)):
		print(mat[i])

def factor(n):
	d = collections.defaultdict(int)
	while not n % 2:
		d[2] += 1
		n //= 2
	i = 3
	while i * i <= n:
		while not n % i:
			d[i] += 1
			n //= i
		i += 2
	if n > 1:
		d[n] += 1
	return d

@repeat(times=getint())
def main():
	n = getint()
	pfactors = factor(n)
	if 1 in pfactors:
		del pfactors[1]
	a = []
	for (k, v) in pfactors.items():
		a.extend([k] * v)
	a.sort(key=lambda x: (-pfactors[x], x))
	stack = [a[0]]
	for c in a[1:]:
		if c % stack[-1] != 0:
			last = stack.pop()
			stack.append(last * c)
			continue
		stack.append(c)
	print(len(stack))
	print(*stack)
main()


inf = 100005
pms = []
pr = [1] * inf
for i in range(2, inf):
	if pr[i]:
		pms.append(i)
		for j in range(i * i, inf, i):
			pr[j] = 0
for tt in range(int(input())):
	n = int(input())
	fs = {}
	for p in pms:
		if n % p == 0:
			cnt = 1
			n //= p
			while n % p == 0:
				n //= p
				cnt += 1
			fs[p] = cnt
			if n == 1:
				break
	if n != 1:
		fs[n] = 1
	pfs = list(fs.keys())
	nump = len(pfs)
	mx = max(fs.values())
	dd = []
	for f in pfs:
		dd.append([0] * (mx - fs[f]) + [1] * fs[f])
	ans = [1] * mx
	for i in range(mx):
		for j in range(nump):
			if dd[j][i]:
				ans[i] *= pfs[j]
	print(mx)
	print(*ans)


import math

def solve(n):
	a = []
	b = {}
	d = 0
	while n % 2 == 0:
		n = n / 2
		d += 1
	b[2] = d
	d = 0
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			n = n / i
			d += 1
		b[i] = d
		d = 0
	if n > 2:
		b[int(n)] = 1
	te = max(b.values())
	f = 0
	for i in b.keys():
		if b[i] == te:
			f = i
	print(b[f])
	for i in range(0, b[f] - 1):
		print(f, end=' ')
	return (f, b[f])
t = int(input())
for i in range(0, t):
	a = int(input())
	(c, d) = solve(a)
	print(a // c ** (d - 1))


t = int(input())
p = [2]
for i in range(3, 10 ** 5 + 2, 2):
	for j in range(2, int(i ** 0.5) + 1):
		if i % j == 0:
			break
	else:
		p.append(i)
for _ in range(t):
	n = int(input())
	m = n
	a = []
	for i in p:
		if n % i == 0:
			x = 0
			while n % i == 0:
				x += 1
				n //= i
			a.append((i, x))
	if len(a) == 0:
		a = [(m, 1)]
	(x, k) = a[0]
	for (i, j) in a:
		if j > k:
			k = j
			x = i
	an = [x for i in range(k - 1)] + [m // x ** (k - 1)]
	print(k)
	print(*an)


import math

def solver(n, x):
	a = []
	while n > 0:
		if n / x % x == 0:
			a.append(x)
			n = n // x
		else:
			a.append(n)
			break
	return a
for _ in range(int(input())):
	n = int(input())
	x = n
	l = 0
	ans = []
	for i in range(2, int(math.sqrt(n) + 1)):
		if n % i == 0:
			x = i
			b = []
			b = solver(n, x).copy()
			if l < len(b):
				l = len(b)
				ans = []
				ans = b.copy()
	if l == 0:
		l += 1
		ans.append(n)
	print(l)
	for i in ans:
		print(i, end=' ')
	print()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	m = n
	cnt = Counter()
	if not n % 2:
		while not n % 2:
			cnt[2] += 1
			n //= 2
	i = 3
	while i * i <= n:
		if not n % i:
			while not n % i:
				cnt[i] += 1
				n //= i
		i += 2
	if n > 1:
		cnt[n] += 1
	maxv = max(cnt.values())
	cand = [c for c in cnt if cnt[c] == maxv]
	a = min(cand)
	if m // a % a:
		ans = [m]
	else:
		ans = [a]
		m //= a
		while True:
			if m == 1:
				break
			if m // a % a:
				ans.append(m)
				break
			else:
				ans.append(a)
				m //= a
	print(len(ans))
	print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	temp = n
	num = -1
	count = 0
	i = 2
	while i * i <= n:
		count1 = 0
		while n % i == 0:
			count1 += 1
			n //= i
		if count1 > count:
			count = count1
			num = i
		if i == 2:
			i += 1
		else:
			i += 2
	if num == -1:
		print('1')
		print(temp)
	else:
		print(count)
		ans = list()
		for i in range(count - 1):
			ans.append(num)
			temp = temp // num
		ans.append(temp)
		print(*ans)


from sys import stdout, stdin, maxsize
from collections import defaultdict, deque
import math
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	d = defaultdict(int)
	m = n
	temp = 0
	while n % 2 == 0:
		temp += 1
		n = n // 2
	d[2] = temp
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		temp = 0
		while n % i == 0:
			temp += 1
			n = n // i
		d[i] = temp
	if n > 2:
		d[n] = 1
	M = 0
	ind = 0
	for i in d.keys():
		z = d[i]
		if M < z:
			M = z
			ind = i
	stdout.write(str(M) + '\n')
	for i in range(M - 1):
		stdout.write(str(ind) + ' ')
		m = m // ind
	stdout.write(str(m) + '\n')


from sys import stdin
_input = stdin.readline
(_range, _int, _dict) = (range, int, dict)
from collections import defaultdict

def solution():

	def factorize(digit):
		i = 2
		ans = defaultdict(_int)
		while i * i <= digit:
			if digit % i == 0:
				ans[i] += 1
				digit //= i
			else:
				i += 1
		if digit > 1:
			ans[digit] += 1
		return ans
	for _ in _range(_int(_input())):
		n = _int(_input())
		z = factorize(n)
		ans = -1
		for i in z.keys():
			if z[i] > ans:
				ans = z[i]
				index = i
		if ans == 1:
			print(1)
			print(n)
		else:
			print(z[index])
			for i in _range(z[index] - 1):
				print(index, end=' ')
				n //= index
			print(n)
solution()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
import bisect
from types import GeneratorType
BUFSIZE = 8192

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7
mod = 10 ** 9 + 7
t = int(input())
p = 10 ** 9 + 7

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def z_array(s1):
	n = len(s1)
	z = [0] * n
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and s1[r - l] == s1[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and s1[r - l] == s1[r]:
					r += 1
				z[i] = r - l
				r -= 1
	return z

def primeFactors(n):
	d1 = {}
	while n % 2 == 0:
		d1[2] = d1.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d1[i] = d1.get(i, 0) + 1
			n = n // i
	if n > 2:
		d1[n] = d1.get(n, 0) + 1
	return d1

def solve(n):
	d = primeFactors(n)
	mul = 1
	for i in d:
		mul *= i
	l = []
	for i in d:
		l.append([d[i], i])
	l.sort()
	ans = []
	sub = 0
	for i in range(len(l)):
		l[i][0] -= sub
		for j in range(l[i][0]):
			ans.append(mul)
			sub += 1
		mul //= l[i][1]
	print(len(ans))
	for i in range(len(ans) - 1, -1, -1):
		print(ans[i], end=' ')
	print()
for _ in range(t):
	n = int(input())
	solve(n)


import math
import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		m = n
		divisor = []
		two = 0
		while n % 2 == 0:
			two += 1
			n = n / 2
		if two > 0:
			divisor += [[two, 2]]
		for i in range(3, int(n ** 0.5) + 2, 2):
			curr = [0, i]
			while n % i == 0:
				curr[0] += 1
				n /= i
			if curr[0]:
				divisor += [curr]
		if len(divisor) < 1 and n != 1:
			print(1)
			print(m)
			continue
		divisor = sorted(divisor, key=lambda x: x[0])[::-1]
		x = [divisor[0][1]] * (divisor[0][0] - 1) + [m // int(divisor[0][1] ** (divisor[0][0] - 1))]
		print(len(x))
		print(*x)
main()


from math import sqrt
t = int(input())
for i in range(t):
	k = int(input())
	x1 = k
	if k == 2:
		print(1)
		print(2)
		continue
	ans = float('-inf')
	z = 1
	for j in range(2, int(sqrt(k)) + 1):
		if k % j == 0:
			r = 0
			while k % j == 0:
				r = r + 1
				k = k // j
			ans = max(ans, r)
			if ans == r:
				z = j
	if ans == float('-inf'):
		print(1)
		print(x1)
		continue
	s1 = str(z) + ' '
	print(ans)
	print(s1 * (ans - 1) + str(x1 // z ** (ans - 1)))


from collections import Counter
import sys
input = sys.stdin.readline

def prog():
	for _ in range(int(input())):
		n = int(input())
		fact = []
		for i in range(2, int(n ** 0.5) + 2):
			if n % i == 0:
				while n % i == 0:
					fact.append(i)
					n //= i
		if n > 1:
			fact.append(n)
		b = Counter(fact)
		most_appearances = b.most_common(1)[0][0]
		seq = [most_appearances] * b[most_appearances]
		for i in b:
			if i != most_appearances:
				for j in range(b[i]):
					seq[-1] *= i
		print(len(seq))
		print(*seq)
prog()


t = int(input())
for _ in range(t):
	n = int(input())
	dels = []
	ans = []
	mxlen = 0
	mxans = []
	for i in range(2, n // 2 + 1):
		if i > 100000.0:
			break
		if n % i == 0:
			dels.append(i)
	for d in dels:
		m = n
		ans = []
		if d != 0:
			while True:
				if m // d % d == 0:
					m //= d
					ans.append(d)
				else:
					ans.append(m)
					break
		if len(ans) > mxlen:
			mxans = ans
			mxlen = len(ans)
	if mxans == []:
		mxans.append(n)
	print(len(mxans))
	print(*mxans)


import sys
from collections import defaultdict
input = lambda : sys.stdin.readline().strip()

def get_primes(n):
	ans = defaultdict(int)
	while n % 2 == 0:
		ans[2] += 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			ans[i] += 1
			n = n // i
	if n > 2:
		ans[n] += 1
	return ans
t = int(input())
while t:
	t -= 1
	n = int(input())
	primes = get_primes(n)
	(prime, k) = max(primes.items(), key=lambda x: x[1])
	a = [prime] * k
	del primes[prime]
	for key in primes:
		a[-1] *= key ** primes[key]
	print(k)
	print(*a)


from math import sqrt

def solve(n):
	ans = n
	cnt = 1
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			m = n
			t = 0
			while m % i == 0:
				t += 1
				m //= i
			if t > cnt:
				ans = i
				cnt = t
	return (ans, cnt)
for cnt in range(int(input())):
	n = int(input())
	(x, cnt) = solve(n)
	print(cnt)
	while n % x == 0:
		n //= x
		if n % x != 0:
			print(n * x)
		else:
			print(x, end=' ')


from collections import defaultdict
import math

def len(d):
	count = 0
	for jj in d:
		count += 1
	return count
for _ in range(int(input())):
	n = int(input())
	no = n
	d = defaultdict(int)
	(i, m, index) = (2, 0, -1)
	while i * i <= n:
		c = 0
		while n % i == 0:
			c += 1
			n = n // i
		d[i] += c
		if m < d[i]:
			index = i
			m = d[i]
		i = i + 1
	if no == 2:
		print(1)
		print(2, end=' ')
	elif no == 3:
		print(1)
		print(3, end=' ')
	elif no == 5:
		print(1)
		print(5, end=' ')
	elif no == 4:
		print(2)
		print(2, 2, end=' ')
	elif d[index] == 0:
		print(1)
		print(no, end=' ')
	elif no == index ** d[index]:
		print(d[index])
		for j in range(d[index]):
			print(int(index), end=' ')
	else:
		print(d[index])
		for j in range(d[index] - 1):
			print(int(index), end=' ')
		print(abs(int(no // index ** (d[index] - 1))), end=' ')
	print()


def solve():
	n = int(input())
	k = 0
	res = []
	for i in range(2, 34):
		counter = 2
		while counter ** i <= n:
			if n % counter ** i == 0:
				if i > k:
					k = i
					res = [counter] * (i - 1) + [n // counter ** (i - 1)]
					break
			counter += 1
	if k == 0:
		print(1)
		print(n)
	else:
		print(k)
		print(' '.join(map(str, res)))
for _ in range(int(input())):
	solve()


from math import *
from collections import *
for u in range(int(input())):
	n = int(input())
	x = n
	l = []
	for i in range(2, int(sqrt(x)) + 1):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 1:
		l.append(n)
	m = len(l)
	y = list(set(l))
	y.sort()
	d = defaultdict(list)
	q = []
	ll = []
	for i in l:
		for j in range(len(y)):
			if i % y[j] == 0:
				d[y[j]].append(i)
	for i in d:
		ll.append([len(d[i]), d[i]])
	ll.sort(reverse=True)
	f = ll[0][1]
	for i in range(1, len(ll)):
		for j in ll[i][1]:
			if j not in f:
				f.append(j)
	l = f
	s = m
	p = 1
	for i in range(1, m):
		if l[i] % l[i - 1] != 0:
			s = i - 1
			break
		else:
			p = p * l[i - 1]
	if s == m:
		print(len(l))
		print(*l)
	else:
		p = l[:s] + [x // p]
		print(len(p))
		print(*p)


import math
from collections import defaultdict as dt

def primeFactors(n):
	d = dt(lambda : 0)
	c = 0
	e = -1
	m = n
	while n % 2 == 0:
		d[2] = d[2] + 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[i] = d[i] + 1
			n = n / i
	if n > 2:
		d[n] = d[n] + 1
	for i in d:
		if d[i] > c:
			c = d[i]
			e = i
	print(c)
	x = 1
	for i in range(c - 1):
		x = x * e
		print(e, end=' ')
	print(m // x)
for _ in range(int(input())):
	n = int(input())
	primeFactors(n)


for _ in range(int(input())):
	n = int(input())
	temp = n
	sequence = []
	d = {}
	res = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			while n % i == 0:
				n = n // i
				sequence.append(i)
	if n > 1:
		sequence.append(n)
	for item in sequence:
		d[item] = d.get(item, 0) + 1
	d = sorted(d.items(), key=lambda x: x[1], reverse=True)
	cnt = d[0][1]
	while cnt > 1:
		res.append(d[0][0])
		temp //= d[0][0]
		cnt -= 1
	res.append(temp)
	print(len(res))
	print(' '.join(map(str, res)))


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	m = n
	i1 = int(sqrt(n)) + 1
	l1 = [0 for i in range(i1 + 1)]
	f1 = 0
	ma = 0
	i2 = -1
	i = 2
	while i <= i1 and n > 1:
		if n % i == 0:
			l1[i] += 1
			n = n // i
			if l1[i] > ma:
				ma = l1[i]
				i2 = i
			f1 = 1
		else:
			i += 1
	if f1 == 0 or ma == 1:
		print(1)
		print(m)
	else:
		print(ma)
		for _ in range(ma - 1):
			print(i2, end=' ')
		print(m // i2 ** (ma - 1))


from collections import defaultdict

def prime(n, d):
	if n == 1:
		return
	for i in range(2, int(n ** 0.5) + 1):
		while n % i == 0:
			d[i] += 1
			n = n // i
	if n > 1:
		d[n] += 1
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(lambda : 0)
	prime(n, d)
	ans = []
	m = max(d.values())
	for i in d.keys():
		if d[i] == m:
			ans = [i] * (d[i] - 1)
	c = 1
	for i in ans:
		c = c * i
	ans.append(n // c)
	print(len(ans))
	print(*ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

def PrimeFactorization(x):

	def plist(x):
		if x < 2:
			return []
		if x & 1 == 0:
			return [2] + plist(x >> 1)
		for p in range(3, x + 1, 2):
			if x % p == 0:
				return [p] + plist(x // p)
			if p ** 2 > x:
				return [x]
	pl = plist(x)
	(pp, ee) = ([], [])
	for p in pl:
		if not pp or p != pp[-1]:
			pp += [p]
			ee += [0]
		ee[-1] += 1
	return (pp, ee)
for _ in range(II()):
	n = II()
	(pp, ee) = PrimeFactorization(n)
	m = max(ee)
	aa = [1] * m
	for (p, e) in zip(pp, ee):
		aa[m - e] *= p
	for i in range(m - 1):
		aa[i + 1] *= aa[i]
	print(len(aa))
	print(*aa)


import os
import sys
from io import BytesIO, IOBase
import math

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def calmaxpow(n, i):
	f = 0
	while n % i == 0:
		n //= i
		f += 1
	return f
for xyz in range(0, int(input())):
	n = int(input())
	root = int(n ** 0.5)
	cmp = 0
	fac = n
	for i in range(2, root + 1):
		if n % i == 0:
			(f1, f2) = (i, n // i)
			(m1, m2) = (calmaxpow(n, f1), calmaxpow(n, f2))
			if m1 > cmp:
				cmp = m1
				fac = f1
			if m2 > cmp:
				cmp = m2
				fac = f2
	print(max(1, cmp))
	t = 1
	for i in range(0, cmp - 1):
		print(fac, end=' ')
		t *= fac
	print(n // t)


import math

def primeFactors(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n // i
	if n > 2:
		ans.append(int(n))
	return ans
for _ in range(int(input())):
	n = int(input())
	data = primeFactors(n)
	bag = dict()
	for q in data:
		bag[q] = bag.get(q, 0) + 1
	maximum = 0
	ans = 0
	for (key, value) in bag.items():
		if value > maximum:
			ans = key
			maximum = value
	print(maximum)
	for q in range(maximum - 1):
		print(ans, end=' ')
	temp_ans = 1
	for (key, value) in bag.items():
		if key == ans:
			temp_ans *= key
		else:
			temp_ans = temp_ans * key ** value
	print(temp_ans)


from collections import Counter

def is_prime(n):
	if n == 2:
		return True
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return False

def prime(n):
	res = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			cntr = 0
			while n % i == 0:
				res.append(i)
				n //= i
	if n != 1:
		res.append(n)
	return res

def arr(res, n):
	x = Counter(res)
	x = x.most_common()
	y = x[0][0]
	count = x[0][1] - 1
	return [count, y]
for _ in range(int(input())):
	n = int(input())
	if is_prime(n):
		print(1)
		print(n)
	else:
		res = prime(n)
		array = arr(res, len(res))
		x = array[0]
		if x == 0:
			print(1)
			print(n)
		else:
			y = array[1]
			another = []
			while len(another) < x:
				res.remove(y)
				another.append(y)
			j = 1
			for i in res:
				j *= i
			print(len(another) + 1)
			print(*another, j)


import sys
r = sys.stdin.readline
for _ in range(int(r())):
	N = int(r())
	NN = N + 0
	dic = {}
	for i in range(2, int(N ** 0.5 + 2)):
		while N % i == 0:
			N //= i
			try:
				dic[i] += 1
			except:
				dic[i] = 1
	dicL = sorted(dic.items(), key=lambda x: -x[1])
	if dicL:
		if dicL[0][1] == 1:
			answer = 1
			answerL = [NN]
		else:
			answer = dicL[0][1]
			answerL = [dicL[0][0]] * dicL[0][1]
			answerL[-1] = answerL[0] * (NN // answerL[0] ** dicL[0][1])
	else:
		answer = 1
		answerL = [NN]
	print(answer)
	for i in answerL:
		print(i, end=' ')
	print()