An agent called Cypher is decrypting a message, that contains a composite number $n$. All divisors of $n$, which are greater than $1$, are placed in a circle. Cypher can choose the initial order of numbers in the circle.

In one move Cypher can choose two adjacent numbers in a circle and insert their least common multiple between them. He can do that move as many times as needed.

A message is decrypted, if every two adjacent numbers are not coprime. Note that for such constraints it's always possible to decrypt the message.

Find the minimal number of moves that Cypher should do to decrypt the message, and show the initial order of numbers in the circle for that.


-----Input-----

The first line contains an integer $t$ $(1 \le t \le 100)$ — the number of test cases. Next $t$ lines describe each test case.

In a single line of each test case description, there is a single composite number $n$ $(4 \le n \le 10^9)$ — the number from the message.

It's guaranteed that the total number of divisors of $n$ for all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case in the first line output the initial order of divisors, which are greater than $1$, in the circle. In the second line output, the minimal number of moves needed to decrypt the message.

If there are different possible orders with a correct answer, print any of them.


-----Example-----
Input
3
6
4
30

Output
2 3 6 
1
2 4 
0
2 30 6 3 15 5 10 
0



-----Note-----

In the first test case $6$ has three divisors, which are greater than $1$: $2, 3, 6$. Regardless of the initial order, numbers $2$ and $3$ are adjacent, so it's needed to place their least common multiple between them. After that the circle becomes $2, 6, 3, 6$, and every two adjacent numbers are not coprime.

In the second test case $4$ has two divisors greater than $1$: $2, 4$, and they are not coprime, so any initial order is correct, and it's not needed to place any least common multiples.

In the third test case all divisors of $30$ greater than $1$ can be placed in some order so that there are no two adjacent numbers that are coprime.

Source: codeforces | Difficulty: MEDIUM


Solutions:
import random
from math import gcd, sqrt, floor, ceil

def solve_1(n):
	d = divisors(n)
	order = [0] * len(d)
	moves = [999999999] * 1
	mark = [False] * len(d)
	permutation(d, [0] * len(d), 0, moves, mark, order)
	if gcd(order[0], order[-1]) == 1:
		moves[0] += 1
	return (order, moves[0])

def permutation(d, p, pos, moves, mark, order):
	if pos == len(d):
		m = 0
		for i in range(len(p) - 1):
			if gcd(p[i], p[i + 1]) == 1:
				m += 1
		if m < moves[0]:
			moves[0] = m
			for i in range(len(p)):
				order[i] = p[i]
		return
	for i in range(len(d)):
		if not mark[i]:
			mark[i] = True
			p[pos] = d[i]
			permutation(d, p, pos + 1, moves, mark, order)
			mark[i] = False
	return

def divisors(n):
	d = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d.insert(floor(len(d) / 2), i)
			if i * i != n:
				d.insert(ceil(len(d) / 2), n // i)
	d.append(n)
	return d

def solve_2(n):
	d = divisors(n)
	moves = 0
	if len(d) == 1:
		return (d, 0)
	order = sort(d)
	if gcd(order[0], order[len(order) - 1]) == 1:
		moves += 1
	return (order, moves)

def sort(d):
	order = []
	order.append(d[0])
	count = len(d)
	d.remove(d[0])
	j = 0
	while len(order) < count:
		if int(gcd(d[j], order[-1])) != 1:
			order.append(d[j])
			d.remove(d[j])
			j = 0
		else:
			j += 1
	return order

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		(order, moves) = solve_2(n)
		print(' '.join((str(j) for j in order)))
		print(moves)
	return

def random_cases():
	n = random.randint(2, 50)
	print('Case: \n' + 'n = ' + str(n))
	(order, moves) = solve_1(n)
	print(' '.join((str(i) for i in order)))
	print(moves)
	return

def tester():
	for i in range(1, 20):
		n = random.randint(4, 50)
		(order_1, moves_1) = solve_1(n)
		(order_2, moves_2) = solve_2(n)
		print('Case ' + str(i) + ':\n' + 'n = ' + str(n))
		print('solucion fuerza bruta : \n' + ' '.join((str(i) for i in order_1)) + '\n' + str(moves_1))
		print('solucion eficiente : \n' + ' '.join((str(i) for i in order_2)) + '\n' + str(moves_2))
		for i in range(min(len(order_1), len(order_2))):
			if order_1[i] != order_2[i] or len(order_1) != len(order_2) or moves_1 != moves_2:
				print(Color.RED + 'Wrong Answer\n' + Color.RESET)
				return
		print(Color.GREEN + 'Accepted\n' + Color.RESET)
	return
main()


import os
import sys
from io import BytesIO, IOBase

def main():
	from math import sqrt, ceil
	for _ in range(int(input())):
		n = int(input())
		factors = [n]
		primeFactors = []
		for i in range(2, ceil(sqrt(n)) + 2):
			if n % i == 0 and factors[-1] != i:
				factors.append(i)
				if i != n // i:
					factors.append(n // i)
		isPrime = [True] * len(factors)
		factors.sort()
		for i in range(len(factors)):
			for j in range(i):
				if factors[i] % factors[j] == 0:
					isPrime[i] = False
					break
		for i in range(len(factors)):
			if isPrime[i]:
				primeFactors.append(factors[i])
		if len(primeFactors) <= 1:
			print(' '.join(map(str, factors)))
			print(0)
		elif len(factors) == 3 and factors[1] % factors[0] != 0:
			print(' '.join(map(str, factors)))
			print(1)
		elif len(primeFactors) == 2:
			a = primeFactors[0]
			b = primeFactors[1]
			ans = [a * b]
			i = 1
			while n % a ** i == 0:
				ans.append(a ** i)
				i += 1
			for elem in factors:
				if elem % a == 0 and elem % b == 0 and (elem != a * b):
					ans.append(elem)
			i = 1
			while n % b ** i == 0:
				ans.append(b ** i)
				i += 1
			print(' '.join(map(str, ans)))
			print(0)
		else:
			isCovered = [False] * len(factors)
			ans = []
			for i in range(len(primeFactors)):
				a = primeFactors[i]
				ans.append(a)
				for j in range(len(factors)):
					elem = factors[j]
					if elem % a == 0 and elem != a and (elem != a * primeFactors[(i + 1) % len(primeFactors)]) and (elem != a * primeFactors[i - 1]) and (not isCovered[j]):
						ans.append(elem)
						isCovered[j] = True
				ans.append(a * primeFactors[(i + 1) % len(primeFactors)])
			print(' '.join(map(str, ans)))
			print(0)
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()


from itertools import product

def p_factorization_t(n):
	if n == 1:
		return []
	pf_cnt = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			pf_cnt.append((i, cnt))
	if temp != 1:
		pf_cnt.append((temp, 1))
	return pf_cnt

def main():
	ansl = []
	for _ in range(int(input())):
		n = int(input())
		facs = p_factorization_t(n)
		if len(facs) == 1:
			(p, cnt) = facs[0]
			al = []
			for i in range(1, cnt + 1):
				al.append(pow(p, i))
			print(*al)
			print(0)
		ff = []
		pd = {}
		ps = []
		for (p, cnt) in facs:
			row = []
			for i in range(0, cnt + 1):
				row.append(pow(p, i))
			ff.append(row)
			pd[p] = []
			ps.append(p)
		vals = [1]
		for row in ff:
			new_vals = []
			for v in vals:
				for p in row:
					new_vals.append(p * v)
					if p != 1:
						pd[row[1]].append(v * p)
			vals = new_vals[:]
		if len(facs) >= 3:
			al = []
			for i in range(len(ps)):
				cval = -1
				if i > 0:
					cval = ps[i] * ps[i - 1]
					al.append(cval)
				else:
					cval = ps[i] * ps[-1]
				for v in pd[ps[i]]:
					if v != cval:
						al.append(v)
			print(*al)
			print(0)
		elif len(facs) == 2:
			al = []
			for i in range(len(ps)):
				cval = -1
				if i > 0:
					cval = ps[i] * ps[i - 1]
					al.append(cval)
				else:
					cval = ps[i] * ps[-1]
				for v in pd[ps[i]]:
					if v != cval:
						al.append(v)
			print(*al)
			if facs[0][1] == 1 and facs[1][1] == 1:
				print(1)
			else:
				print(0)

def __starting_point():
	main()
__starting_point()


def gen(i, cur):
	global dvs, used
	if i == len(kk):
		if (ohne != 1 or cur != 1) and (ok or not used[cur * ohne]):
			dvs.append(cur * ohne)
		return
	gen(i + 1, cur)
	for j in range(kk[i]):
		cur *= pp[i]
		gen(i + 1, cur)
gans = []
for _ in range(int(input())):
	n = int(input())
	pp = []
	kk = []
	i = 2
	cnt = []
	while i * i <= n:
		if n % i == 0:
			pp.append(i)
			kk.append(0)
			while n % i == 0:
				kk[-1] += 1
				n //= i
		i += 1
	if n != 1:
		pp.append(n)
		kk.append(1)
	dvs = []
	ohne = 1
	ok = True
	gen(0, 1)
	if len(pp) == 1:
		gans.append(' '.join(map(str, dvs)))
		gans.append(str(0))
	elif len(pp) == 2 and kk[0] == kk[1] == 1:
		gans.append(' '.join(map(str, dvs)))
		gans.append(str(1))
	elif len(pp) == 2:
		used = dict()
		for i in range(len(dvs)):
			used[dvs[i]] = False
		ans = []
		ok = False
		used[pp[0] * pp[1]] = True
		aaa = [pp[0] * pp[1]]
		if kk[0] > 1:
			used[pp[0] * pp[0] * pp[1]] = True
			aaa.append(pp[0] * pp[0] * pp[1])
		else:
			used[pp[0] * pp[1] * pp[1]] = True
			aaa.append(pp[0] * pp[1] * pp[1])
		for i in range(len(pp)):
			dvs = []
			ans.append(aaa[i])
			kk[i] -= 1
			ohne = pp[i]
			gen(0, 1)
			for j in range(len(dvs)):
				used[dvs[j]] = True
				ans.append(dvs[j])
		gans.append(' '.join(map(str, ans)))
		gans.append(str(0))
	else:
		used = dict()
		for i in range(len(dvs)):
			used[dvs[i]] = False
		ans = []
		ok = False
		for i in range(len(pp)):
			used[pp[i - 1] * pp[i]] = True
		for i in range(len(pp)):
			dvs = []
			ans.append(pp[i - 1] * pp[i])
			kk[i] -= 1
			ohne = pp[i]
			gen(0, 1)
			for j in range(len(dvs)):
				used[dvs[j]] = True
				ans.append(dvs[j])
		gans.append(' '.join(map(str, ans)))
		gans.append(str(0))
print('\n'.join(gans))


from os import path
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

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

def si():
	return input().rstrip()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('a')

def ceil(a, b):
	return (a + b - 1) // b
file = 1

def f():
	sys.stdout.flush()

def func(p1, q1):
	ans = []
	for i in range(1, q1 + 1):
		ans.append(p1 ** i)
	return ans

def solve():
	for _ in range(ii()):
		n = ii()
		n1 = n
		cntdivisor = 1
		divisor = []
		for i in range(2, int(sqrt(n)) + 1):
			c = 0
			while n % i == 0:
				c += 1
				n //= i
			if c > 0:
				cntdivisor *= c + 1
				divisor.append([i, c])
		if n > 1:
			divisor.append([n, 1])
			cntdivisor *= 2
		ans = func(divisor[0][0], divisor[0][1])
		n = len(divisor)
		for i in range(1, n):
			p = divisor[i][0]
			q = divisor[i][1]
			tmp = func(p, q)
			n = len(ans)
			lcm = p * ans[-1]
			ans.append(lcm)
			ans += tmp[1:]
			for j in range(n):
				for k in tmp:
					if k * ans[j] == lcm:
						continue
					if k * ans[j] == n1 and n > 2:
						continue
					ans.append(k * ans[j])
			ans.append(p)
		if len(divisor) == 2:
			if len(ans) == 3:
				print(*ans)
				print(1)
			else:
				(ans[-2], ans[-1]) = (ans[-1], ans[-2])
				print(*ans)
				print(0)
		elif len(divisor) == 1:
			print(*ans)
			print(0)
		else:
			ans.append(n1)
			print(*ans)
			print(0)
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
solve()


n = 40000 + 1
primes = []
sieve = [1] * n
for i in range(2, n):
	if sieve[i]:
		primes.append(i)
		for j in range(i * i, n, i):
			sieve[j] = 0

def all_fct(l):
	ret = [1]
	for (p, q) in l:
		pp = 1
		l_ret = len(ret)
		for _ in range(q):
			pp *= p
			ret.extend((ret[i] * pp for i in range(l_ret)))
	return ret
for tt in range(int(input())):
	n = int(input())
	nn = n
	ff = []
	cnt = 0
	for p in primes:
		while nn % p == 0:
			cnt += 1
			nn //= p
		if cnt > 0:
			ff.append((p, cnt))
			cnt = 0
			if n == 1:
				break
	if nn != 1:
		ff.append((nn, 1))
	ans = []
	kk = len(ff)
	if kk == 1:
		print(' '.join(map(str, [a for a in all_fct(ff) if a != 1])))
		print(0)
		continue
	elif kk == 2 and max(ff[0][1], ff[1][1]) == 1:
		print(' '.join(map(str, [ff[0][0], ff[1][0], ff[0][0] * ff[1][0]])))
		print(1)
		continue
	transition = {}
	for i in range(kk):
		transition[ff[i][0] * ff[(i + 1) % kk][0]] = i
	if kk == 2:
		if ff[0][1] > 1:
			transition[ff[0][0] * ff[0][0] * ff[1][0]] = 0
		else:
			transition[ff[0][0] * ff[1][0] * ff[1][0]] = 0
	all_f = all_fct(ff)
	ans = [[] for i in range(kk)]
	for f in all_f:
		if f not in transition:
			for ind in range(kk):
				if f % ff[ind][0] == 0:
					ans[ind].append(f)
					break
	for tr in transition:
		ans[transition[tr]].append(tr)
	ans_ = []
	for aa in ans:
		ans_.extend(aa)
	print(' '.join(map(str, ans_)))
	print(0)


from math import sqrt
from collections import deque

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def factors(n):
	d = deque()
	e = deque()
	for x in range(2, int(sqrt(n) + 1)):
		if n % x == 0:
			d.append(x)
			if n // x != x:
				e.append(n // x)
	e.append(n)
	for x in range(len(e)):
		d.append(e[x])
	m = {}
	for x in range(len(d)):
		m[d[x]] = 1
	return (d, m)
t = int(input())
while t:
	n = int(input())
	(fa, m) = factors(n)
	l = len(fa)
	a = [-1] * l
	ans = [-1] * l
	ans[0] = fa[0]
	m[fa[0]] = 0
	y = 1
	for x in range(1, l):
		if m[fa[x]]:
			if gcd(ans[y - 1], fa[x]) > 1:
				ans[y] = fa[x]
				m[fa[x]] = 0
				y += 1
			else:
				ans[y] = ans[y - 1] * fa[x]
				m[fa[x]] = 0
				m[ans[y - 1] * fa[x]] = 0
				y += 1
				ans[y] = fa[x]
				y += 1
	for x in range(l):
		print(ans[x], end=' ')
	print()
	if gcd(ans[-1], ans[0]) == 1:
		print(1)
	else:
		print(0)
	t -= 1


import itertools
import math
import sys
from collections import defaultdict

def stdinWrapper():
	data = '4\n6\n4\n30\n1000000000\n'
	for line in data.split('\n'):
		yield line
if '--debug' not in sys.argv:

	def stdinWrapper():
		while True:
			yield input()
inputs = stdinWrapper()

def inputWrapper():
	return next(inputs)

def getType(_type):
	return _type(inputWrapper())

def getArray(_type):
	return [_type(x) for x in inputWrapper().split()]

def is_prime(num):
	if num == 1 or num == 2:
		return True
	div = 2
	while True:
		if num % div == 0:
			return False
		if div * div > num:
			break
		div += 1
	return True

def solve(a):
	divisors = []
	for x in range(2, a):
		if x * x > a:
			break
		if a % x == 0:
			divisors.append(x)
			divisors.append(a // x)
	divisors.append(a)
	primes = set()
	for x in divisors:
		if is_prime(x):
			primes.add(x)
	primes = list(primes)
	divisors = sorted(list(set(divisors)))
	if len(divisors) == 3 and is_prime(divisors[0]) and is_prime(divisors[1]):
		return (1, divisors)
	result = {}
	for i in range(len(primes)):
		result[primes[i - 1]] = [primes[i - 1]]
		divisors.remove(primes[i - 1])
		prod = primes[i - 1] * primes[i]
		if prod in divisors:
			divisors.remove(prod)
			result[primes[i - 1]].append(prod)
		else:
			for d in list(divisors):
				if d % primes[i - 1] == 0 and d % primes[i] == 0:
					divisors.remove(d)
					result[primes[i - 1]].append(d)
					break
	while divisors:
		d = divisors.pop()
		for p in result:
			if d % p == 0:
				result[p].insert(0, d)
				break
	final_result = []
	for x in sorted(result.keys()):
		final_result += result[x]
	return (0, final_result)
t = getType(int)
for _ in range(t):
	n = getType(int)
	(k, arr) = solve(n)
	print(' '.join([str(x) for x in arr]))
	print(k)


import itertools
y = lambda : int(input())
p = [1] * 32000
for i in range(180):
	if p[i]:
		for j in range(2 * i + 2, len(p), i + 2):
			p[j] = 0
q = [i + 2 for i in range(len(p)) if p[i]]
for _ in range(y()):
	n = y()
	d = []
	e = set()
	for i in q:
		if n % i < 1:
			n //= i
			d.append([i, 1])
			while n % i < 1:
				n //= i
				d[-1][1] += 1
	if n > 1:
		d.append([n, 1])
	l = len(d)
	for i in itertools.product(*(range(i[1] + 1) for i in d)):
		p = 1
		for j in range(l):
			p *= d[j][0] ** i[j]
		e.add(p)
	e.remove(1)
	b = l == 2 and d[0][1] + d[1][1] == 2
	if l < 2 or b:
		f = list(e)
	elif l < 3:
		s = d[1][1] > 1
		v = d[s][0] * d[1 - s][0]
		f = [v]
		e.remove(v)
		k = set()
		for i in e:
			if i % d[1 - s][0] < 1:
				k.add(i)
				f.append(i)
		v = d[s][0] ** 2 * d[1 - s][0]
		f.remove(v)
		f.append(v)
		e -= k
		for i in e:
			f.append(i)
	else:
		v = d[0][0] * d[-1][0]
		f = [v]
		e.remove(v)
		for i in range(l):
			v = d[i][0] * d[i - 1][0]
			f.remove(v)
			f.append(v)
			k = set()
			for j in e:
				if j % d[i][0] < 1:
					k.add(j)
					f.append(j)
			e -= k
	print(' '.join(map(str, f)))
	print(int(b))


import io
import os
from collections import Counter, defaultdict, deque

def divisors(n):
	front = []
	back = []
	for x in range(1, int(n ** 0.5) + 1):
		if n % x == 0:
			front.append(x)
			back.append(n // x)
	if front[-1] == back[-1]:
		front.pop()
	return front + back[::-1]

def primeFactors(n):
	assert n >= 1
	factors = Counter()
	while n % 2 == 0:
		factors[2] += 1
		n //= 2
	x = 3
	while x * x <= n:
		while n % x == 0:
			factors[x] += 1
			n //= x
		x += 2
	if n != 1:
		factors[n] += 1
	return factors

def solve(N):
	divs = divisors(N)
	divs.remove(1)
	factors = primeFactors(N)
	if len(factors) == 2 and all((v == 1 for v in factors.values())):
		moves = 1
		circle = divs
	else:
		keys = set(factors.keys())
		circle = []
		p = next(iter(keys))
		firstP = p
		lastP = None
		keys.remove(p)
		while divs:
			group = []
			rest = []
			for d in divs:
				if d % p == 0:
					group.append(d)
				else:
					rest.append(d)
			circle += group
			divs = rest
			for k in keys:
				if group[-1] % k == 0:
					p = k
					keys.remove(p)
					lastP = p
					break
		if lastP is not None:
			circle.remove(firstP * lastP)
			circle.append(firstP * lastP)
		moves = 0
	return ' '.join(map(str, circle)) + '\n' + str(moves)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	ans = solve(N)
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for you in range(t):
	n = int(input())
	z = n
	primes = []
	i = 2
	while i * i <= z:
		if z % i == 0:
			primes.append(i)
			while z % i == 0:
				z = z // i
		i += 1
	if z != 1:
		primes.append(z)
	hashi = dict()
	for i in primes:
		hashi[i] = []
	hashinew = dict()
	new = []
	k = len(primes)
	hasho = dict()
	if k > 2:
		for i in range(k):
			new.append(primes[i] * primes[(i + 1) % k])
			hasho[primes[i] * primes[(i + 1) % k]] = 1
	if k == 2:
		hasho[primes[0] * primes[1]] = 1
	i = 2
	while i * i <= n:
		if n % i == 0:
			num1 = i
			num2 = n // i
			if num1 not in hasho:
				for j in primes:
					if num1 % j == 0:
						break
				hashi[j].append(num1)
			if num2 != num1 and num2 not in hasho:
				for j in primes:
					if num2 % j == 0:
						break
				hashi[j].append(num2)
		i += 1
	for j in primes:
		if n % j == 0:
			break
	hashi[j].append(n)
	done = dict()
	if len(primes) == 1:
		for i in hashi[primes[0]]:
			print(i, end=' ')
		print()
		print(0)
		continue
	if len(primes) == 2:
		if primes[0] * primes[1] == n:
			print(primes[0], primes[1], n)
			print(1)
		else:
			for i in hashi[primes[0]]:
				print(i, end=' ')
			for i in hashi[primes[1]]:
				print(i, end=' ')
			print(primes[0] * primes[1], end=' ')
			print()
			print(0)
		continue
	for i in range(k):
		for j in hashi[primes[i]]:
			print(j, end=' ')
		ko = primes[i] * primes[(i + 1) % k]
		print(ko, end=' ')
	print()
	print(0)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
import string

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
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.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, self.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')

def get_int():
	return int(input())

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

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().strip()

def get_strs():
	return get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

def prime_facts(m):
	facts = {}
	mult = 0
	while m % 2 == 0:
		mult += 1
		m //= 2
	if mult:
		facts[2] = mult
	i = 3
	while m > 1 and i * i <= m:
		mult = 0
		while m % i == 0:
			mult += 1
			m //= i
		if mult:
			facts[i] = mult
		i += 2
	if m > 1:
		facts[m] = 1
	return facts

def facts(m):
	i = 1
	f = set()
	while i * i <= m:
		if m % i == 0:
			f.add(i)
			f.add(m // i)
		i += 1
	return f

def solve_e():
	n = get_int()
	pf = prime_facts(n)
	p_list = list(pf.keys())
	if len(pf) == 2 and max(pf.values()) == 1:
		return ([p_list[0], p_list[1], n], 1)
	f = facts(n)
	f.remove(1)
	if len(pf) == 1:
		ans = [p_list[0]]
		f.remove(p_list[0])
	elif len(pf) == 2:
		(p, q) = pf.keys()
		ans = [p, n, q, p * q]
		f.remove(p)
		f.remove(n)
		f.remove(q)
		f.remove(p * q)
	else:
		ans = []
		for i in range(len(p_list)):
			ans.append(p_list[i])
			ans.append(p_list[i] * p_list[(i + 1) % len(p_list)])
			f.remove(p_list[i])
			f.remove(p_list[i] * p_list[(i + 1) % len(p_list)])
	for factor in f:
		for (idx, p) in enumerate(pf):
			if factor % p == 0:
				jdx = ans.index(p)
		ans.insert(jdx + 1, factor)
	return (ans, 0)
t = get_int()
for _ in range(t):
	(arr, m) = solve_e()
	print(*arr)
	print(m)


import math

def get_divisors(n):
	ret = set()
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				ret.add(i)
			else:
				ret.add(i)
				ret.add(n // i)
		i += 1
	return ret
for _ in range(int(input())):
	n = int(input())
	o = n
	primes = {}
	while n % 2 == 0:
		if 2 in primes:
			primes[2] += 1
		else:
			primes[2] = 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i in primes:
				primes[i] += 1
			else:
				primes[i] = 1
			n = n // i
	if n > 2:
		primes[n] = 1
	if len(primes) == 1:
		p = list(primes.keys())[0]
		for i in range(primes[p]):
			print(p ** (i + 1), end=' ')
		print()
		print(0)
	elif len(primes) == 2:
		l = list(primes.keys())
		p1 = l[0]
		p2 = l[1]
		e1 = primes[p1]
		e2 = primes[p2]
		if e1 == 1 and e2 == 1:
			print(p1, p2, p1 * p2)
			print(1)
		elif e1 >= e2:
			for i in range(e2):
				print(p2 ** (i + 1), end=' ')
			print(p2 * p1, end=' ')
			for i in range(1, e1 + 1):
				for j in range(e2 + 1):
					if j == 1 and (i == 1 or i == 2):
						continue
					print(p1 ** i * p2 ** j, end=' ')
			print(p2 * p1 ** 2)
			print(0)
		else:
			for i in range(e1):
				print(p1 ** (i + 1), end=' ')
			print(p2 * p1, end=' ')
			for i in range(1, e2 + 1):
				for j in range(e1 + 1):
					if j == 1 and (i == 1 or i == 2):
						continue
					print(p2 ** i * p1 ** j, end=' ')
			print(p1 * p2 ** 2)
			print(0)
	else:
		divisors = get_divisors(o)
		divisors.remove(1)
		ans = []
		keys = list(primes.keys())
		for k in range(len(keys)):
			p = keys[k]
			nextp = keys[(k + 1) % len(keys)]
			curr = o // p
			divs = get_divisors(curr)
			l = {p * x for x in divs}
			l.remove(p * nextp)
			if k == 0:
				l.remove(p * keys[len(keys) - 1])
				divisors.remove(p * keys[len(keys) - 1])
			for el in l:
				if el in divisors:
					ans.append(el)
					divisors.remove(el)
			ans.append(p * nextp)
			if p * nextp in divisors:
				divisors.remove(p * nextp)
		print(*ans)
		print(0)


import os, sys
from io import BytesIO, IOBase
from collections import Counter

def main():
	for _ in range(int(input())):
		n = int(input())
		fac = Counter()
		div = {n}
		x = n
		for i in range(2, int(x ** 0.5) + 1):
			if not x % i:
				div.add(i)
				div.add(x // i)
			while not n % i:
				fac[i] += 1
				n //= i
		if n != 1:
			fac[n] += 1
		x = list(fac.keys())
		if len(fac) == 1:
			print(' '.join(map(str, div)))
			print(0)
		elif sum(fac.values()) == 2 and len(fac) == 2:
			print(x[0], x[0] * x[1], x[1])
			print(1)
		else:
			fir = []
			for i in range(len(x)):
				su = x[i] * x[i - 1]
				for j in div:
					if not j % su:
						fir.append(j)
						break
				div.remove(fir[-1])
			ans = []
			for (ind, val) in enumerate(x):
				ans.append(fir[ind])
				nu = 0
				for j in div:
					if not j % val:
						nu += 1
						ans.append(j)
				for j in range(-1, -1 - nu, -1):
					div.remove(ans[j])
			print(' '.join(map(str, ans)))
			print(0)
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()


from collections import defaultdict

def check_prime(n):
	i = 2
	if n == 2 or n == 3:
		return True
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True
t = int(input())
for z in range(t):
	n = int(input())
	factors = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			factors.append(i)
			factors.append(n // i)
		i += 1
	factors = list(set(factors))
	factors.sort()
	factors.append(n)
	if len(factors) == 3 and check_prime(factors[0]) and check_prime(factors[1]):
		print(*factors)
		print(1)
		continue
	primes = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			primes.append(i)
			while n % i == 0:
				n = n // i
		i += 1
	if n > 1:
		primes.append(n)
	answer = [0] * len(primes)
	visited = defaultdict(lambda : False)
	for i in range(len(primes)):
		p = primes[i]
		q = primes[(i + 1) % len(primes)]
		for j in factors:
			if not visited[j] and j % p == 0 and (j % q == 0):
				visited[j] = True
				answer[i] = j
				break
	for i in range(len(primes)):
		p = primes[i]
		print(p, end=' ')
		visited[p] = True
		for j in factors:
			if not visited[j] and j % p == 0:
				print(j, end=' ')
				visited[j] = True
		if len(primes) > 1:
			print(answer[i], end=' ')
	print()
	print(0)


for _ in range(int(input())):
	n = int(input())
	pfacs = []
	(m, i) = (n, 2)
	while i * i <= m:
		while m % i == 0:
			pfacs.append(i)
			m //= i
		i += 1
	if m > 1:
		pfacs.append(m)
	pr = list(set(pfacs))
	facs = {1}
	for p in pfacs:
		facs |= set((p * x for x in facs))
	facs.remove(1)

	def get():
		global facs
		if len(pr) == 1:
			return (facs, 0)
		if len(pr) == 2:
			(p, q) = pr
			if len(pfacs) == 2:
				return ([p, q, n], 1)
			pmul = set((x for x in facs if x % p == 0))
			facs -= pmul
			pmul -= {p, p * q, n}
			facs.remove(q)
			return ([p, *pmul, p * q, q, *facs, n], 0)
		ans = []
		for (p, q) in zip(pr, pr[1:] + [pr[0]]):
			pmul = set((x for x in facs if x % p == 0))
			if p == pr[0]:
				pmul.remove(p * pr[-1])
			facs -= pmul
			pmul -= {p, p * q}
			ans += [p, *pmul, p * q]
		return (ans, 0)
	(ans, c) = get()
	print(*ans)
	print(c)


import sys, os, io
input = sys.stdin.readline
from collections import defaultdict, deque

def factorize(n):
	b = 2
	dic = defaultdict(lambda : 0)
	while b * b <= n:
		while n % b == 0:
			n //= b
			dic[b] += 1
		b = b + 1
	if n > 1:
		dic[n] += 1
	return dic

def divisor(n):
	cd = [n]
	i = 2
	while i * i <= n:
		if n % i == 0:
			cd.append(i)
			if i != n // i:
				cd.append(n // i)
		i += 1
	cd.sort()
	return cd
T = int(input())
for t in range(T):
	N = int(input())
	fac = factorize(N)
	kvs = list(fac.items())
	ans = []
	deq = deque([])
	if len(kvs) == 1:
		(k, v) = kvs[0]
		a = 1
		for _ in range(v):
			a *= k
			ans.append(a)
		print(*ans)
		print(0)
		continue
	ans.append(N)
	kvs2 = kvs[1:] + [kvs[0]]
	for ((k, v), (k1, v1)) in zip(kvs, kvs2):
		a = 1
		for _ in range(v):
			a *= k
			ans.append(a)
			deq.appendleft(a)
		if k1 == kvs[0][0]:
			break
		for _ in range(len(deq)):
			b = deq.popleft()
			deq.append(b)
			for _ in range(v1):
				b *= k1
				if b != N:
					ans.append(b)
					deq.append(b)
	print(*ans)
	if len(kvs) == 2 and kvs[0][1] == kvs[1][1] == 1:
		print(1)
	else:
		print(0)


t = int(input())
for _ in range(t):
	works = 0
	n = int(input())
	ps = []
	for i in range(2, 4 * 10 ** 4):
		c = 0
		while n % i == 0:
			c += 1
			n //= i
		if c:
			ps.append((i, c))
	if n > 1:
		ps.append((n, 1))
	if len(ps) >= 3:
		base = [0] * (2 * len(ps))
		lists = [[] for i in range(2 * len(ps))]
		for i in range(len(ps)):
			base[2 * i] = ps[i][0]
			base[2 * i + 1] = ps[i][0] * ps[(i + 1) % len(ps)][0]
			factors = [1]
		for (p, pp) in ps:
			mult = [pow(p, i) for i in range(pp + 1)]
			new = []
			for m in mult:
				for f in factors:
					new.append(m * f)
			factors = new
		for v in factors:
			if v in base:
				lists[base.index(v)] += [v]
			else:
				for u in range(2 * len(ps)):
					if v % base[u] == 0:
						lists[u] += [v]
						break
		out = sum(lists, [])
	elif len(ps) == 2:
		(p, q) = ps
		if p[1] < q[1]:
			(p, q) = (q, p)
		(p, pp) = p
		(q, qq) = q
		if pp == 1 and qq == 1:
			works = 1
			out = [p, p * q, q]
		else:
			base = [p, p * q, q, p * p * q]
			lists = [[], [], [], []]
			for i in range(pp + 1):
				for j in range(qq + 1):
					v = pow(p, i) * pow(q, j)
					if v in base:
						lists[base.index(v)] += [v]
					else:
						for u in range(4):
							if v % base[u] == 0:
								lists[u] += [v]
								break
			out = sum(lists, [])
	else:
		out = []
		for i in range(1, ps[0][1] + 1):
			out.append(pow(ps[0][0], i))
	print(' '.join(map(str, out)))
	print(works)


def get_divisors(n):
	i = 2
	ans = [n]
	while i * i <= n:
		if n % i == 0:
			ans.append(i)
			other = n // i
			if other != i:
				ans.append(other)
		i += 1
	return ans

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

def lcm(a, b):
	return a * b // gcd(a, b)

def link(group1, group2):
	for i in range(len(group1)):
		if group1[i] % group2[0] == 0:
			(group1[i], group1[-1]) = (group1[-1], group1[i])
			return True
	return False

def link2(group1, group2):
	for i in range(len(group1) - 1):
		if group1[i] % group2[0] == 0:
			(group1[i], group1[0]) = (group1[0], group1[i])
			return True
	return False
for _ in range(int(input())):
	n = int(input())
	divisors = sorted(get_divisors(n))
	groups = []
	while divisors:
		removed = []
		remained = []
		for v in divisors:
			if v % divisors[0] == 0:
				removed.append(v)
			else:
				remained.append(v)
		divisors = remained
		groups.append(removed)
	if len(groups) == 1:
		print(*groups[0])
		print(0)
	else:
		links = 0
		for i in range(len(groups) - 1):
			second_group = groups[(i + 1) % len(groups)]
			if link(groups[i], second_group):
				links += 1
		if len(groups) > 1 and link2(groups[0], groups[-1]):
			links += 1
		res = []
		for group in groups:
			res.extend(group)
		print(*res)
		print(len(groups) - links)


from collections import defaultdict as dd, deque

def factor(n):
	factors = dd(int)
	d = 2
	while d * d <= n:
		while n % d == 0:
			factors[d] += 1
			n //= d
		d += 1
	if n != 1:
		factors[n] += 1
	return factors

def divisors(n):
	i = 1
	factors = []
	while i * i <= n:
		if n % i == 0:
			if n // i == i:
				factors.append(i)
			else:
				factors.append(i)
				factors.append(n // i)
		i += 1
	return factors
t = int(input())
for _ in range(t):
	n = int(input())
	F = factor(n)
	D = set(divisors(n))
	D.remove(1)
	if len(F) == 1:
		print(*list(D))
		print(0)
		continue
	if len(F) == 2:
		(p, q) = list(F)
		exp = sum(F.values())
		if exp > 2:
			res = []
			D.remove(p * q)
			D.remove(p * p * q)
			divP = {d for d in D if d % p == 0}
			divQ = D - divP
			print(p * q, *divP, p * p * q, *divQ)
			print(0)
		else:
			print(p, p * q, q)
			print(1)
		continue
	first = 1
	for prime in F:
		first *= prime
	D.remove(first)
	Flist = list(F)
	res = [first]
	for i in range(len(Flist) - 1):
		(p, q) = (Flist[i - 1], Flist[i])
		D.remove(p * q)
	for i in range(len(Flist) - 1):
		(p, q) = (Flist[i - 1], Flist[i])
		div = {d for d in D if d % p == 0}
		D -= div
		res.extend(div)
		res.append(p * q)
	res.extend(D)
	print(*res)
	print(0)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
from functools import reduce
from collections import defaultdict
import math

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

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

def gift():
	for _ in range(t):
		n = int(input())
		factList = list(factors(n))
		factList = sorted(factList)[1:]
		primeDic = defaultdict(lambda : [])
		primeLis = []
		for ele in factList:
			if isPrime(ele):
				primeDic[ele].append(ele)
				primeLis.append(ele)
			else:
				for key in primeDic:
					if ele % key == 0:
						primeDic[key].append(ele)
						break
		m = len(primeLis)
		freeToGoLis = []
		freeToGo = defaultdict(lambda : [])
		for i in range(m):
			currPrime = primeLis[i]
			nextPrime = primeLis[(i + 1) % m]
			if len(primeDic[currPrime]) > 2:
				counter = 0
				for ele in primeDic[currPrime]:
					if ele % nextPrime != 0 and ele != currPrime or counter >= 2:
						freeToGo[ele] = currPrime
					else:
						counter += 1
			else:
				for ele in freeToGo:
					if ele % currPrime == 0 and ele % nextPrime == 0:
						where = freeToGo[ele]
						del freeToGo[ele]
						primeDic[where].remove(ele)
						primeDic[currPrime].append(ele)
						break
		ans = []
		for ele in primeDic:
			ans.extend(primeDic[ele])
		res = 0
		leni = len(factList)
		for i in range(leni):
			currPrime = ans[i]
			nextPrime = ans[(i + 1) % leni]
			if math.gcd(currPrime, nextPrime) == 1:
				res += 1
		yield ' '.join([str(x) for x in ans])
		yield res
t = int(input())
ans = gift()
print(*ans, sep='\n')


from collections import defaultdict

def setup():
	import os, sys
	dir_path = os.path.dirname(os.path.realpath(__file__))
	sys.stdin = open(os.path.join(dir_path, 'input.txt'), 'r')
	sys.stdout = open(os.path.join(dir_path, 'output.txt'), 'w')

def divisors(n: int) -> list:
	divisors = []
	i = 1
	while i * i < n:
		if n % i == 0:
			divisors.append(i)
		i += 1
	if i * i == n:
		divisors.append(i)
	prev_i = i - 1
	for i in range(prev_i, 0, -1):
		if n % i == 0:
			divisors.append(n // i)
	return divisors

def prime_factors(n: int) -> list:
	s = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			n //= i
			if not s or s[-1] != i:
				s.append(i)
		else:
			i += 1
	if n > i:
		s.append(n)
	return s

def solve(n):
	primes = prime_factors(n)
	divs = divisors(n)[1:]
	if len(primes) == 1:
		return (divs, 0)
	if len(primes) == 2:
		if len(divs) == 3:
			return (divs, 1)
		(p0, p1) = primes
		if n % p0 ** 2 == 0:
			(p0, p1) = (p1, p0)
		divs = [i for i in divs if i not in {p0, p1, p0 * p1, p0 * p1 ** 2}]
		return ([p0, p0 * p1 ** 2] + divs + [p1, p0 * p1], 0)
	div_to_spf = {d: prime for d in divs for prime in primes[::-1] if d % prime == 0}
	for i in range(len(primes)):
		del div_to_spf[primes[i]]
		div_to_spf.pop(primes[i] * primes[i - 1], None)
	spf_to_div = defaultdict(list)
	for (div, spf) in div_to_spf.items():
		spf_to_div[spf].append(div)
	ans = []
	for i in range(len(primes)):
		ans.append(primes[i] * primes[i - 1])
		ans.append(primes[i])
		ans.extend(spf_to_div[primes[i]])
	return (ans, 0)
for _ in range(int(input())):
	(arr, num) = solve(int(input()))
	print(' '.join(list(map(str, arr))))
	print(num)


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.readline())

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

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

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

def SI():
	return sys.stdin.readline()[:-1]

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)

def factors(a):
	if a <= 0:
		return [0]
	res = []
	for d in range(1, a + 1):
		if d * d > a:
			break
		if a % d:
			continue
		res.append(d)
		res.append(a // d)
	if res[-1] == res[-2]:
		res.pop()
	return res
for _ in range(II()):
	a = II()
	(pp, ee) = PrimeFactorization(a)
	if len(pp) == 1:
		print(' '.join((str(pp[0] ** (i + 1)) for i in range(ee[0]))))
		print(0)
		continue
	if len(pp) == 2:
		if ee[0] == ee[1] == 1:
			print(pp[0], pp[1], a)
			print(1)
		else:
			pp0 = [pp[0] ** (i + 1) for i in range(ee[0])]
			pp1 = [pp[1] ** (i + 1) for i in range(ee[1])]
			ans = pp0 + [pp[0] * pp[1]] + pp1
			for p0 in pp0:
				for p1 in pp1:
					if p0 * p1 == pp[0] * pp[1]:
						continue
					ans.append(p0 * p1)
			print(*ans)
			print(0)
		continue
	n = len(pp)
	aa = [[] for _ in range(n)]
	bb = [[] for _ in range(n)]
	for f in factors(a):
		for i in range(n):
			d = pp[i] * pp[i - 1]
			if f % d == 0:
				bb[i].append(f)
				break
		else:
			for i in range(n):
				if f % pp[i] == 0:
					aa[i].append(f)
					break
	ans = []
	for (ar, br) in zip(aa, bb):
		ans += br + ar
	print(*ans)
	print(0)


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

def str(x=b''):
	return x if type(x) is bytes else _str(x).encode()

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')

def inp():
	return sys.stdin.readline()

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

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

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = gcd(abs(x - y), n)
				if f != n:
					return f
	return n

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def is_prime(n):
	if n < 5 or n & 1 == 0 or n % 3 == 0:
		return 2 <= n <= 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			p = p * p % n
			if p == n - 1:
				break
		else:
			return False
	return True

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def is_coprime(a, b):
	return gcd(a, b) == 1

def solve():
	n = itg()
	factors = set(all_factors(n)[1:])
	size = len(factors)
	if size == 2:
		print(*factors)
		return 0
	primes = []
	for f in tuple(factors):
		if is_prime(f):
			primes.append(f)
			factors.remove(f)
	if size == 3:
		if len(primes) == 1:
			p = primes[0]
			print(p, p * p, n)
			return 0
		print(*primes, n)
		return 1
	if len(primes) == 2:
		m = primes[0] * primes[1]
		last = {primes[0]: m}
		factors.remove(m)
		m *= primes[0]
		if m not in factors:
			m = m // primes[0] * primes[1]
		last[primes[1]] = m
		factors.remove(m)
	else:
		last = {primes[-1]: primes[0] * primes[-1]}
		factors.remove(primes[0] * primes[-1])
		for i in range(len(primes) - 1):
			p1 = primes[i]
			p2 = primes[i + 1]
			m = p1 * p2
			last[p1] = m
			factors.remove(m)
	d = {p: [p] for p in primes}
	for f in factors:
		r = pollard_rho(f)
		while not is_prime(r):
			r = pollard_rho(r)
		d[r].append(f)
	for (k, v) in last.items():
		d[k].append(v)
	result = []
	for k in sorted(d.keys()):
		result.extend(d[k])
	print(*result)
	return 0
DEBUG = 0
if not DEBUG:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
for _ in range(itg()):
	print(solve())


import random
import math

def solve(n):
	d = divisors(n)
	moves = 0
	if len(d) == 1:
		return (d, 0)
	order = sort(d)
	if math.gcd(order[0], order[len(order) - 1]) == 1:
		moves += 1
	return (order, moves)

def divisors(n):
	d = []
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			d.append(i)
			if i * i != n:
				d.append(n // i)
	d.append(n)
	d.sort()
	return d

def lcm(a, b):
	return a * b // math.gcd(a, b)

def sort(d):
	order = []
	order.append(d[0])
	count = len(d)
	d.remove(d[0])
	j = 0
	while len(order) < count:
		if math.gcd(d[j], order[-1]) != 1:
			order.append(d[j])
			d.remove(d[j])
			j = 0
		else:
			j += 1
	return order

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		(order, moves) = solve(n)
		print(' '.join((str(j) for j in order)))
		print(moves)
	return
main()


def iinput():
	return [int(i) for i in input().split()]

def prime_factorization(x):
	factorization = []
	t = 2
	while t * t <= x:
		if not x % t:
			cur = 0
			while not x % t:
				x //= t
				cur += 1
			factorization.append([t, cur])
		t += 1
	if x > 1:
		factorization.append([x, 1])
	return factorization

def factors(prime_factors):
	factors1 = []
	for i in prime_factors:
		cur = []
		for j in range(i[1] + 1):
			cur += [i[0] ** j]
		factors1.append(cur)
	while len(factors1) > 1:
		cur_f = factors1.pop()
		cur_s = factors1.pop()
		cur_th = []
		for i in cur_f:
			for j in cur_s:
				cur_th += [i * j]
		factors1.append(cur_th)
	return factors1[0][1:]
t = int(input())
for _ in range(t):
	n = int(input())
	fact = prime_factorization(n)
	if len(fact) == 2 and fact[0][1] == fact[1][1] and (fact[0][1] == 1):
		print(fact[0][0], fact[1][0], fact[0][0] * fact[1][0])
		print(1)
	elif len(fact) == 2 and (fact[0][1] == 1 or fact[1][1] == 1):
		all_factors = factors(fact)
		fact = [i[0] for i in fact]
		black_list = []
		ans = []
		lena = len(fact)
		extra = 0
		first = fact[0]
		second = fact[1]
		for i in range(lena):
			cur = fact[i]
			next = fact[(i + 1) % lena]
			black_list += [cur]
			black_list += [next]
		for i in all_factors:
			if i != first * second and (not i % first) and (not i % second):
				extra = i
				black_list += [i]
				break
		for i in range(lena):
			ans += [fact[i]]
			cur = fact[i]
			next = fact[(i + 1) % lena]
			for i in all_factors:
				if not i % cur and i not in black_list and (i != cur * next):
					ans += [i]
					black_list += [i]
			if cur * next not in black_list:
				ans += [cur * next]
				black_list += [cur * next]
			else:
				ans += [extra]
		print(*ans)
		print(0)
	else:
		all_factors = factors(fact)
		fact = [i[0] for i in fact]
		black_list = []
		ans = []
		lena = len(fact)
		for i in range(lena):
			cur = fact[i]
			next = fact[(i + 1) % lena]
			black_list += [cur]
			black_list += [next]
			black_list += [cur * next]
		for i in range(lena):
			ans += [fact[i]]
			cur = fact[i]
			next = fact[(i + 1) % lena]
			for i in all_factors:
				if not i % cur and i not in black_list:
					ans += [i]
					black_list += [i]
			ans += [cur * next]
		print(*ans)
		print(0)


from collections import defaultdict as d
MAXPRIME = 32000
isPrime = [0 for _ in range(MAXPRIME + 1)]
isPrime[0] = -1
isPrime[1] = -1
for i in range(2, MAXPRIME // 2):
	if isPrime[i] == 0:
		for multiple in range(i * i, MAXPRIME + 1, i):
			if isPrime[multiple] == 0:
				isPrime[multiple] = i
primeNumberSet = set()
for i in range(len(isPrime)):
	if isPrime[i] == 0:
		primeNumberSet.add(i)

def generateAllFactors(idx, product):
	if idx == len(primeFactors):
		if product > 1:
			allFactors.add(product)
	else:
		for i in range(counts[idx] + 1):
			generateAllFactors(idx + 1, product * primeFactors[idx] ** i)
t = int(input())
for _ in range(t):
	n = int(input())
	initialN = n
	p = d(lambda : 0)
	for x in primeNumberSet:
		if n % x == 0:
			cnt = 0
			while n % x == 0:
				cnt += 1
				n //= x
			p[x] = cnt
	if n != 1:
		p[n] = 1
	primeFactors = []
	counts = []
	allFactors = set()
	for (k, v) in p.items():
		primeFactors.append(k)
		counts.append(v)
	generateAllFactors(0, 1)
	ans = []
	nMoves = 0
	for i in range(1, len(primeFactors) + 1):
		a = primeFactors[i - 1]
		if i < len(primeFactors):
			b = primeFactors[i]
		else:
			b = primeFactors[0]
		if a == b:
			ans.append(a)
			allFactors.remove(a)
			break
		else:
			if a * b in allFactors:
				ans.append(a * b)
				allFactors.remove(a * b)
			elif a * a * b in allFactors:
				ans.append(a * a * b)
				allFactors.remove(a * a * b)
			elif a * b * b in allFactors:
				ans.append(a * b * b)
				allFactors.remove(a * b * b)
			else:
				nMoves += 1
			ans.append(b)
			allFactors.remove(b)
	for x in allFactors:
		for i in range(len(ans)):
			if x % ans[i] == 0:
				break
		ans.insert(i + 1, x)
	s = ' '.join([str(x) for x in ans])
	print(s)
	print(nMoves)


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')

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def get_divisors(n):
	ret = set()
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				ret.add(i)
			else:
				ret.add(i)
				ret.add(n // i)
		i += 1
	return ret
for _ in range(int(input())):
	n = int(input())
	o = n
	primes = {}
	while n % 2 == 0:
		if 2 in primes:
			primes[2] += 1
		else:
			primes[2] = 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			if i in primes:
				primes[i] += 1
			else:
				primes[i] = 1
			n = n // i
	if n > 2:
		primes[n] = 1
	if len(primes) == 1:
		p = list(primes.keys())[0]
		for i in range(primes[p]):
			print(p ** (i + 1), end=' ')
		print()
		print(0)
	elif len(primes) == 2:
		l = list(primes.keys())
		p1 = l[0]
		p2 = l[1]
		e1 = primes[p1]
		e2 = primes[p2]
		if e1 == 1 and e2 == 1:
			print(p1, p2, p1 * p2)
			print(1)
		elif e1 >= e2:
			for i in range(e2):
				print(p2 ** (i + 1), end=' ')
			print(p2 * p1, end=' ')
			for i in range(1, e1 + 1):
				for j in range(e2 + 1):
					if j == 1 and (i == 1 or i == 2):
						continue
					print(p1 ** i * p2 ** j, end=' ')
			print(p2 * p1 ** 2)
			print(0)
		else:
			for i in range(e1):
				print(p1 ** (i + 1), end=' ')
			print(p2 * p1, end=' ')
			for i in range(1, e2 + 1):
				for j in range(e1 + 1):
					if j == 1 and (i == 1 or i == 2):
						continue
					print(p2 ** i * p1 ** j, end=' ')
			print(p1 * p2 ** 2)
			print(0)
	else:
		divisors = get_divisors(o)
		divisors.remove(1)
		ans = []
		keys = list(primes.keys())
		for k in range(len(keys)):
			p = keys[k]
			nextp = keys[(k + 1) % len(keys)]
			curr = o // p
			divs = get_divisors(curr)
			l = {p * x for x in divs}
			l.remove(p * nextp)
			if k == 0:
				l.remove(p * keys[len(keys) - 1])
				divisors.remove(p * keys[len(keys) - 1])
			for el in l:
				if el in divisors:
					ans.append(el)
					divisors.remove(el)
			ans.append(p * nextp)
			if p * nextp in divisors:
				divisors.remove(p * nextp)
		print(*ans)
		print(0)


import sys

def I():
	return int(sys.stdin.readline().rstrip())
t = I()
for _ in range(t):
	n = I()
	divisor = [n]
	prime = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			divisor.append(i)
			if i != n // i:
				divisor.append(n // i)
	n0 = n
	for i in range(2, int(n ** 0.5) + 1):
		if n0 % i == 0:
			prime.append(i)
			while n0 % i == 0:
				n0 //= i
	if n0 != 1:
		prime.append(n0)
	m = len(prime)
	if m == 1:
		print(*divisor)
		print(0)
	elif m >= 3:
		ANS1 = [[] for _ in range(m)]
		ANS2 = [prime[i] * prime[i + 1] for i in range(m - 1)] + [prime[m - 1] * prime[0]]
		for d in divisor:
			if d in ANS2:
				continue
			else:
				for i in range(m):
					if d % prime[i] == 0:
						ANS1[i].append(d)
						break
		ANS = []
		for i in range(m):
			ANS += ANS1[i]
			ANS += [ANS2[i]]
		print(*ANS)
		print(0)
	elif len(divisor) == 3:
		print(*divisor)
		print(1)
	else:
		(ANS1, ANS2, ANS3) = ([], [], [prime[0] * prime[1]])
		if prime[0] ** 2 * prime[1] in divisor:
			ANS3.append(prime[0] ** 2 * prime[1])
		else:
			ANS3.append(prime[1] ** 2 * prime[0])
		for d in divisor:
			if d in ANS3:
				continue
			elif d % prime[0] == 0:
				ANS1.append(d)
			else:
				ANS2.append(d)
		ANS = ANS1 + [ANS3[0]] + ANS2 + [ANS3[1]]
		print(*ANS)
		print(0)


import math
import random

def cnt(x):
	fac = {}
	y = x
	while x > 1:
		i = 2
		flag = False
		while i * i <= x:
			if x % i == 0:
				fac[i] = 0
				while x % i == 0:
					x //= i
					fac[i] += 1
				flag = True
				break
			i += 1
		if not flag:
			fac[x] = 1
			break
	f = set()
	i = 2
	while i * i <= y:
		if y % i == 0:
			f.add(i)
			if y // i != i:
				f.add(y // i)
		i += 1
	f.add(y)
	return (fac, f)
t = int(input())
while t:
	n = int(input())
	(mp, f) = cnt(n)
	primes = list(mp.keys())
	if len(primes) == 1:
		for x in f:
			print(x, end=' ')
		print('\n0')
	elif len(primes) == 2:
		if mp[primes[0]] == 1 and mp[primes[1]] == 1:
			print(primes[0], primes[1], n)
			print(1)
		else:
			(a, b) = primes
			print(a, a * b, b, end=' ')
			f.discard(a)
			f.discard(a * b)
			f.discard(b)
			for i in range(2, mp[b] + 1):
				print(b ** i, end=' ')
			for i in range(1, mp[b] + 1):
				for j in range(1, mp[a] + 1):
					if i != 1 or j != 1:
						print(b ** i * a ** j, end=' ')
			for i in range(2, mp[a] + 1):
				print(a ** i, end=' ')
			print('\n0')
	else:
		for i in range(len(primes)):
			(a, b) = (primes[i], primes[(i + 1) % len(primes)])
			f.discard(a)
			f.discard(a * b)
		ff = {}
		for p in primes:
			ff[p] = set()
			for x in list(f):
				if x % p == 0:
					ff[p].add(x)
					f.discard(x)
		for i in range(len(primes)):
			(a, b) = (primes[i], primes[(i + 1) % len(primes)])
			print(a, end=' ')
			for v in ff[a]:
				print(v, end=' ')
			print(a * b, end=' ')
		print('\n0')
	t -= 1


import math
T = int(input())

def construct1(a, p):
	v = 1
	for i in range(0, p[0]):
		v = v * a[0]
		print(v, end=' ')
	print(a[1] * a[0], end=' ')
	v = 1
	for i in range(1, p[1] + 1):
		v = v * a[1]
		vv = v
		for j in range(0, p[0] + 1):
			if i != 1 or j != 1:
				print(vv, end=' ')
			vv = vv * a[0]
	print()
	print(0)

def construct2(a, p):
	m = len(a)
	spe = a[0] * a[m - 1]

	def dfs(x, v):
		if x >= m:
			if v != spe and v != 1:
				print(v, end=' ')
			return 0
		t = v
		for i in range(p[x] + 1):
			dfs(x + 1, v)
			v = v * a[x]
	for i in range(m):
		v = 1
		for j in range(p[i]):
			v = v * a[i]
			dfs(i + 1, v)
	print(spe)
	print(0)
for Tid in range(T):
	n = int(input())
	s = 2
	a = []
	p = []
	while s * s <= n:
		if n % s == 0:
			a.append(s)
			t = 0
			while n % s == 0:
				n = n // s
				t = t + 1
			p.append(t)
		s = s + 1
	if n != 1:
		a.append(n)
		p.append(1)
	type = 0
	if len(a) == 1:
		v = 1
		for i in range(p[0]):
			v = v * a[0]
			print(v, end=' ')
		print()
		print(0)
	else:
		type = 0
		if p[0] == 1 and p[1] == 1 and (len(a) == 2):
			print(a[0], a[1], a[0] * a[1])
			print(1)
		elif len(a) == 2:
			construct1(a, p)
		else:
			construct2(a, p)


import random
import math

def solve(n):
	d = divisors(n)
	moves = 0
	if len(d) == 1:
		return (d, 0)
	order = sort(d)
	if math.gcd(order[0], order[len(order) - 1]) == 1:
		moves += 1
	return (order, moves)

def divisors(n):
	d = []
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			d.append(i)
			if i * i != n:
				d.append(n // i)
	d.append(n)
	d.sort()
	return d

def sort(d):
	order = []
	order.append(d[0])
	count = len(d)
	d.remove(d[0])
	j = 0
	while len(order) < count:
		if math.gcd(d[j], order[-1]) != 1:
			order.append(d[j])
			d.remove(d[j])
			j = 0
		else:
			j += 1
	return order

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		(order, moves) = solve(n)
		print(' '.join((str(j) for j in order)))
		print(moves)
	return

def random_cases():
	n = random.randint(2, 50)
	print('Case: \n' + 'n = ' + str(n))
	(order, moves) = solve(n)
	print(' '.join((str(i) for i in order)))
	print(moves)
	return
main()


from collections import defaultdict, deque
T = int(input())
for _ in range(T):
	n = int(input())
	(d, p) = (defaultdict(int), 2)
	while p * p <= n:
		while n % p == 0:
			(d[p], n) = (d[p] + 1, n // p)
		p += 1
	if n > 1:
		d[n] = 1
	ls = [1]
	for (u, cc) in d.items():
		(m, p) = (len(ls), 1)
		for _ in range(cc):
			p *= u
			for v in reversed(ls[0:m]):
				ls.append(v * p)
	if len(ls) > 2:
		(ls[-1], ls[-2]) = (ls[-2], ls[-1])
	move = len(d) == 2 and max(d.values()) == 1
	print(*ls[1:])
	print(1 if move else 0)


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def get_primes(n: int):
	from itertools import chain
	primes = [2, 3]
	is_prime = array('b', (0, 0, 1, 1, 0, 1, 0)) + array('b', (1, 0, 0, 0, 1, 0)) * ((n - 1) // 6)
	for i in chain.from_iterable((range(5, n + 1, 6), range(7, n + 1, 6))):
		if is_prime[i]:
			primes.append(i)
			for j in range(i * 3, n + 1, i * 2):
				is_prime[j] = 0
	return (is_prime, primes)

def main():
	from collections import Counter, defaultdict
	t = int(input())
	ans_a = [''] * t
	(_, primes) = get_primes(10 ** 5)
	for ti in range(t):
		m = n = int(input())
		pfac = Counter()
		for p in primes:
			while m % p == 0:
				pfac[p] += 1
				m //= p
		if m > 1:
			pfac[m] = 1
		keys = sorted(pfac.keys())
		if len(pfac) == 2 and list(pfac.values()) == [1, 1]:
			ans_a[ti] = f'{keys[0]} {keys[1]} {n}\n1'
			continue
		divisors = defaultdict(list)
		d = 2
		while d * d <= n:
			if n % d == 0:
				(x, y) = (d, n // d)
				for p in keys:
					if x % p == 0:
						divisors[p].append(x)
						break
				if x != y:
					for p in keys:
						if y % p == 0:
							divisors[p].append(y)
							break
			d += 1
		ans = []
		for (p1, p2) in zip(keys, keys[1:]):
			ans.append(p1)
			for div in divisors[p1]:
				if div != p1 and div != p1 * p2:
					ans.append(div)
			ans.append(p1 * p2)
		for div in divisors[keys[-1]]:
			ans.append(div)
		ans.append(n)
		ans_a[ti] = ' '.join(map(str, ans)) + '\n0'
	output(*ans_a)
main()


import math
t = int(input())

def printDivisors(curPrimes, curPrime, primeDict, forbidden, printed):
	l = len(curPrimes)
	num = 1
	for i in range(primeDict[curPrime]):
		num *= curPrime
		for j in range(l):
			temp = num * curPrimes[j]
			curPrimes.append(temp)
			if temp not in printed:
				print(int(temp), end=' ')
				printed[temp] = True
	return [curPrimes, printed]
for o in range(t):
	printed = {}
	m = int(input())
	primeList = []
	primeDict = {}
	for i in range(2, math.ceil(math.sqrt(m)) + 1):
		if m % i == 0:
			primeList.append(i)
			primeDict[i] = 0
			while m % i == 0:
				m = m / i
				primeDict[i] = primeDict[i] + 1
	if m != 1:
		primeList.append(m)
		primeDict[m] = 1
	isOne = False
	if len(primeList) == 2:
		if primeDict[primeList[0]] == 1 and primeDict[primeList[1]] == 1:
			isOne = True
	if isOne == True:
		print(int(primeList[1]), int(primeList[1] * primeList[0]), int(primeList[0]))
		print(1)
	elif len(primeList) <= 2:
		if len(primeList) == 1:
			num = 1
			for i in range(primeDict[primeList[0]]):
				num *= primeList[0]
				print(int(num), end=' ')
			print()
			print(0)
		else:
			primeOne = primeList[0]
			primeTwo = primeList[1]
			forbidden1 = 0
			forbidden2 = 0
			if primeDict[primeOne] != 1:
				forbidden1 = primeOne * primeTwo
				forbidden2 = primeOne * primeTwo * primeOne
			else:
				forbidden1 = primeOne * primeTwo
				forbidden2 = primeOne * primeTwo * primeTwo
			print(int(forbidden1), end=' ')
			printed[forbidden1] = True
			d = [1]
			for i in range(primeDict[primeOne]):
				t = d[-1] * primeOne
				d.append(t)
				if t not in printed:
					print(int(t), end=' ')
				printed[t] = True
			print(int(forbidden2), end=' ')
			printed[forbidden2] = True
			cur = 1
			for i in range(primeDict[primeTwo]):
				cur *= primeTwo
				for j in d:
					temp = int(cur * j)
					if temp not in printed:
						print(temp, end=' ')
						printed[temp] = True
			print()
			print(0)
	else:
		curPrimes = [1]
		for i in range(len(primeList) - 1, -1, -1):
			curPrime = primeList[i]
			forbidden = 0
			if i == len(primeList) - 1:
				forbidden = curPrime * primeList[0]
			else:
				forbidden = curPrime * primeList[i + 1]
			print(int(forbidden), end=' ')
			printed[forbidden] = True
			ret = printDivisors(curPrimes, curPrime, primeDict, forbidden, printed)
			curPrimes = ret[0]
			printed = ret[1]
		print()
		print(0)


from sys import stdin, stdout

class Input:

	def __init__(self):
		self.lines = stdin.read().splitlines()
		self.idx = 0

	def line(self):
		try:
			return self.lines[self.idx]
		finally:
			self.idx += 1

	def array(self, sep=' ', cast=int):
		return list(map(cast, self.line().split(sep=sep)))

	def known_tests(self):
		(num_of_cases,) = self.array()
		for case in range(num_of_cases):
			yield self

	def unknown_tests(self):
		while self.idx < len(self.lines):
			yield self

def problem_solver():
	oo = float('inf')

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

	def modpow(a, n, m):
		ans = 1
		while n:
			if n & 1:
				ans = ans * a % m
			n >>= 1
			a = a * a % m
		return ans
	prime_numbers = []

	def primes():
		for p in prime_numbers:
			yield p
		q = prime_numbers[-1] + 1 if len(prime_numbers) else 2
		while True:
			is_prime = True
			for p in prime_numbers:
				if q % p == 0:
					is_prime = False
					break
			if is_prime:
				prime_numbers.append(q)
				yield q
			q += 1

	def prime_factors(n):
		factors = []
		for p in primes():
			if p * p > n:
				break
			if n % p != 0:
				continue
			r = 0
			while n % p == 0:
				r += 1
				n //= p
			factors.append((p, r))
		if n > 1:
			factors.append((n, 1))
		return factors

	def solver(n):
		f = prime_factors(n)
		divs = [1]
		e = [0, 1]
		for (p, r) in f:
			q = 1
			for i in range(r):
				q *= p
				for d in divs[:e[-1]]:
					divs.append(q * d)
			e.append(len(divs))
		for i in range(1, len(e)):
			le = e[i - 1]
			ri = e[i]
			divs[le:ri] = divs[le:ri][::-1]
		if len(divs) > 1:
			(divs[-1], divs[-2]) = (divs[-2], divs[-1])
		print(*divs[1:])
		count = 0
		if len(f) == 2 and len(divs) == 4:
			count = 1
		print(count)
	return solver
try:
	solver = problem_solver()
	for tc in Input().known_tests():
		solver(*tc.array())
except Exception as e:
	import traceback
	traceback.print_exc(file=stdout)


import sys
import math
ii = lambda : sys.stdin.readline().strip()
idata = lambda : [int(x) for x in ii().split()]

def solve():
	n = int(ii())
	simple = []
	dividers = []
	slov = {}
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			dividers += [i]
			if n // i != i:
				dividers += [n // i]
	dividers += [1]
	dividers.sort()
	for i in range(len(dividers) - 1, -1, -1):
		flag = 1
		for j in range(len(simple)):
			if n // dividers[i] % simple[j] == 0 and flag:
				flag = 0
				slov[simple[j]] += [n // dividers[i]]
		if flag:
			simple += [n // dividers[i]]
			slov[n // dividers[i]] = []
	dividers += [n]
	simple.sort()
	if len(simple) == 2:
		if n % pow(simple[0], 2) != 0 and n % pow(simple[1], 2) != 0:
			print(*dividers[1:])
			print(1)
		else:
			slov[simple[0]].remove(n)
			ans = [simple[0]] + slov[simple[0]] + [simple[1]] + slov[simple[1]] + [n]
			print(*ans)
			print(0)
		return
	if len(simple) >= 2:
		s = simple[0] * simple[-1]
		slov[simple[0]].remove(s)
	ans = []
	for j in range(len(simple)):
		ans += [simple[j]]
		d = simple[(j + 1) % len(simple)] * simple[j]
		for i in slov[simple[j]]:
			if i != d and i != simple[j]:
				ans += [i]
		ans += [d]
	print(*ans)
	print(0)
for t in range(int(ii())):
	solve()


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop, heapify
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import lru_cache
M = mod = 998244353

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

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

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

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]

def isprime(n):
	for j in range(2, int(n ** 0.5) + 1):
		if n % j == 0:
			return 0
	return 1
for _ in range(val()):
	n = val()
	l1 = factors(n)[1:]
	l = []
	for j in l1:
		if isprime(j):
			l.append(j)
	l1 = set(l1)
	l1 -= set(l)
	d = defaultdict(set)
	for j in range(len(l)):
		for i in sorted(list(l1)):
			if i % l[j] == 0 and i % l[j - 1] == 0:
				d[tuple(sorted([l[j], l[j - 1]]))].add(i)
				l1.remove(i)
				break
	for j in range(len(l)):
		for i in sorted(list(l1)):
			if i % l[j] == 0 and i % l[j - 1] == 0:
				d[tuple(sorted([l[j], l[j - 1]]))].add(i)
				l1.remove(i)
	only = defaultdict(list)
	for j in range(len(l)):
		for i in sorted(list(l1)):
			if i % l[j] == 0:
				only[l[j]].append(i)
				l1.remove(i)
	fin = []
	if len(l) == 2:
		fin.append(l[0])
		for j in only[l[0]]:
			fin.append(j)
		for i in range(len(l)):
			for j in list(d[tuple(sorted([l[i], l[(i + 1) % len(l)]]))]):
				fin.append(j)
				d[tuple(sorted([l[i], l[(i + 1) % len(l)]]))].remove(j)
				if i != len(l) - 1:
					break
			if i != len(l) - 1:
				fin.append(l[i + 1])
				for j in only[l[i + 1]]:
					fin.append(j)
	else:
		fin.append(l[0])
		for j in only[l[0]]:
			fin.append(j)
		for i in range(len(l)):
			for j in d[tuple(sorted([l[i], l[(i + 1) % len(l)]]))]:
				fin.append(j)
			if i != len(l) - 1:
				fin.append(l[i + 1])
				for j in only[l[i + 1]]:
					fin.append(j)
	ans = 0
	for i in range(len(fin)):
		if math.gcd(fin[i], fin[i - 1]) == 1:
			ans += 1
	print(*fin)
	print(ans)


from math import ceil
t = int(input())
for _ in range(t):
	n = int(input())
	pf = []
	for i in range(2, ceil(n ** 0.5) + 1):
		while n % i == 0:
			pf.append(i)
			n //= i
	if n > 1:
		pf.append(n)
	if len(pf) == 2 and pf[0] != pf[1]:
		print(pf[0], pf[1], pf[0] * pf[1])
		print(1)
	else:
		pg = []
		fac = []
		nfac = []
		while len(pf) > 0:
			p = pf[-1]
			mul = 0
			while len(pf) > 0 and pf[-1] == p:
				pf.pop()
				mul += 1
			pg.append([mul, p])
		pg.sort()
		pg = pg[::-1]
		cur = 0
		if pg[0][0] == 1:
			a = pg[0][1]
			b = pg[1][1]
			c = pg[2][1]
			fac = [a, a * b * c, a * b, b, b * c, c, a * c]
			cur = 3
		else:
			fac = [pg[0][1] ** i for i in range(1, pg[0][0] + 1)]
			cur = 1
		while cur < len(pg):
			mul = pg[cur][0]
			p = pg[cur][1]
			nfac = []
			for i in range(len(fac)):
				if i == 0:
					nfac += [fac[i] * p ** j for j in range(mul, -1, -1)]
				else:
					nfac += [fac[i] * p ** j for j in range(mul + 1)]
			nfac += [p ** i for i in range(1, mul + 1)]
			fac = nfac
			cur += 1
		print(' '.join([str(i) for i in fac]))
		print(0)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	p = set()
	m = n
	for i in range(2, int(m ** 0.5) + 1):
		if m % i == 0:
			p.add(i)
			while m % i == 0:
				m //= i
	if m > 1:
		p.add(m)
	yakusu = set()
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			yakusu.add(i)
			yakusu.add(n // i)
	yakusu.remove(1)
	p = list(p)
	if len(p) == 1:
		print(*list(yakusu))
		print(0)
	elif len(p) == 2 and p[0] * p[1] == n:
		print(*sorted(list(yakusu)))
		print(1)
	else:
		p = sorted(list(p))
		only = [[] for i in range(len(p))]
		and_fac = [-1] * len(p)
		for x in yakusu:
			for i in range(len(p)):
				if x % p[i] == 0 and x % p[(i + 1) % len(p)] == 0 and (and_fac[i] == -1):
					and_fac[i] = x
					break
			else:
				for i in range(len(p)):
					if x % p[i] == 0:
						only[i].append(x)
						break
		for i in range(len(p)):
			only[i].append(and_fac[i])
		ans = []
		for i in range(len(p)):
			ans += only[i]
		print(*ans)
		print(0)


import math

def prs(n):
	a = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				a.append(i)
			else:
				a.append(i)
				a.append(n // i)
		i += 1
	return a

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

def lcm(a, b):
	return a * b / gcd(a, b)

def binarySearch(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return binarySearch(arr, l, mid - 1, x)
		else:
			return binarySearch(arr, mid + 1, r, x)
	else:
		return -1
for _ in range(int(input())):
	n = int(input())
	a = prs(n)
	a.sort()
	a.remove(1)
	c = [False] * len(a)
	b = [0]
	b[0] = a[0]
	cnt = 0
	i = 1
	j = 1
	d = [a[0]]
	c[0] = True
	while i < len(a):
		if not c[i] and gcd(a[i], b[j - 1]) == 1:
			m = lcm(a[i], b[j - 1])
			ind = binarySearch(a, 0, len(a) - 1, m)
			if ind != -1 and (not c[ind]):
				c[ind] = True
				b.append(a[ind])
				d.append(a[ind])
			else:
				cnt += 1
				b.append(m)
			d.append(a[i])
			b.append(a[i])
			j += 2
		elif not c[i]:
			b.append(a[i])
			d.append(a[i])
			j += 1
		i += 1
	i = len(d) - 2
	while i > 0:
		if d[i] < d[i + 1] and d[i] > d[i - 1]:
			if d[i] % d[0] == 0:
				temp = d[i]
				d[i] = d[-1]
				d[-1] = temp
				break
		else:
			break
		i -= 1
	if d[-1] % d[0] != 0:
		cnt += 1
	for i in d:
		print(i, end=' ')
	print()
	print(min(cnt, len(a) - 2))


import sys
input = lambda : sys.stdin.readline().rstrip()

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 61]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret
for _ in range(int(input())):
	n = int(input())
	ret = primeFactor(n)
	m = len(ret)
	s = 1
	a = []
	for i in ret:
		a.append(i)
		s *= ret[i] + 1
	ans = []
	for i in range(m):
		s //= ret[a[i]] + 1
		for j in range(1, ret[a[i]] + 1):
			for k in range(s):
				x = a[i] ** j
				for l in range(i + 1, m):
					(k, t) = divmod(k, ret[a[l]] + 1)
					x *= a[l] ** t
				ans.append(x)
	if gcd(ans[0], ans[-1]) == 1:
		del ans[ans.index(ans[0] * ans[-1])]
		ans.append(ans[0] * ans[-1])
	anss = 0
	for i in range(len(ans) - 1):
		if gcd(ans[i], ans[i + 1]) == 1:
			anss += 1
	print(*ans)
	print(anss)


from sys import stdin, stdout

def decryption(n):
	r1 = []
	r2 = 0
	factor_a = getfactor(n)
	prime_a = getprime(n)
	hs = set()
	prime_dic = {}
	for i in range(len(prime_a)):
		ni = (i + 1) % len(prime_a)
		prime_dic[prime_a[i]] = []
		if prime_a[i] * prime_a[ni] not in hs:
			prime_dic[prime_a[i]].append(prime_a[i] * prime_a[ni])
		hs.add(prime_a[i])
		hs.add(prime_a[ni])
		hs.add(prime_a[i] * prime_a[ni])
	if len(factor_a) > 3 and len(prime_a) == 2:
		for fac in factor_a:
			if fac not in hs:
				p = getoneprime(fac)
				if p == prime_a[0]:
					prime_dic[prime_a[0]] = []
					prime_dic[prime_a[1]].append(prime_a[0] * prime_a[1])
				break
	for fac in factor_a:
		if fac in hs:
			continue
		p = getoneprime(fac)
		prime_dic[p].append(fac)
		hs.add(fac)
	for p in prime_dic:
		r1.append(p)
		prime_dic[p].reverse()
		for f in prime_dic[p]:
			r1.append(f)
	if len(factor_a) == 3 and len(prime_a) == 2:
		r2 = 1
	return [r1, r2]

def getfactor(n):
	factor_a = [n]
	i = 2
	while i * i < n:
		if n % i == 0:
			factor_a.append(i)
			factor_a.append(n // i)
		i += 1
	if i * i == n:
		factor_a.append(i)
	return factor_a

def getprime(n):
	prime_a = []
	i = 2
	while i * i <= n:
		if n % i == 0:
			prime_a.append(i)
			while n % i == 0:
				n //= i
		i += 1
	if n > 1:
		prime_a.append(n)
	return prime_a

def getoneprime(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return i
		i += 1
	return -1
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	res_a = decryption(n)
	stdout.write(' '.join(map(str, res_a[0])) + '\n')
	stdout.write(str(res_a[1]) + '\n')


from math import sqrt, floor, gcd
t = int(input())
w = []
for i in range(t):
	n = int(input())
	N = n
	primes = []
	powers = []
	for i in range(2, floor(sqrt(n) + 1)):
		if n % i == 0:
			power = 0
			while n % i == 0:
				power = power + 1
				n = n // i
			primes.append(i)
			powers.append(power)
	if n != 1:
		primes.append(n)
		powers.append(1)
	if len(powers) == 1:
		rr = []
		for i in range(powers[0]):
			rr.append(primes[0] ** (i + 1))
		rr.append(0)
		w.append(rr)
	elif len(primes) == 2 and powers[0] == 1 and (powers[1] == 1):
		rr = [primes[0], primes[1], N, 1]
		w.append(rr)
	else:
		rr = []
		k = 1
		for i in primes:
			if len(rr) == 0:
				for i in range(powers[0]):
					rr.append(primes[0] ** (i + 1))
			else:
				rrr = rr[::-1]
				for j in range(powers[k]):
					divisors = map(lambda divisor: divisor * i ** (j + 1), rrr)
					ddivisors = list(divisors)
					for gg in ddivisors:
						rr.append(gg)
				for ff in range(powers[k]):
					rr.append(i ** (ff + 1))
				k = k + 1
		if gcd(rr[0], rr[-1]) == 1:
			lll = rr.index(rr[0] * rr[-1])
			xx = rr[-1]
			xxx = rr[lll]
			rr[lll] = xx
			rr[-1] = xxx
		rr.append(0)
		w.append(rr)
for i in w:
	d = i[-1]
	i.remove(i[-1])
	print(*i)
	print(d)


import math
from functools import reduce
from collections import defaultdict
import sys
input = sys.stdin.readline

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

def divisors(num):
	x = set(reduce(list.__add__, ([i, n // i] for i in range(2, int(math.sqrt(num)) + 1) if num % i == 0)))
	x.add(n)
	return list(x)
t = int(input())
for ii in range(t):
	n = int(input())
	div = divisors(n)
	pfact = primeFactors(n)
	l = list(pfact)
	if len(pfact) == 2 and l[0] * l[1] == n:
		div = ' '.join(map(str, div))
		sys.stdout.write(div + '\n')
		sys.stdout.write('1' + '\n')
	else:
		fac = defaultdict(list)
		for i in div:
			if i != n:
				for j in pfact:
					if i % j == 0:
						fac[j].append(i)
						break
		ans = [n]
		keys = list(fac.keys())
		for i in range(len(keys) - 1):
			tmp = []
			for j in fac[keys[i]]:
				if j != keys[i] * keys[i + 1]:
					tmp.append(int(j))
			tmp.append(int(keys[i] * keys[i + 1]))
			ans += tmp
		for i in fac[keys[-1]]:
			ans.append(i)
		ans = ' '.join(map(str, ans))
		sys.stdout.write(ans + '\n')
		sys.stdout.write('0' + '\n')


from functools import reduce
from math import sqrt
from operator import mul
from sys import stdin, gettrace, stderr
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	n = int(inputi())
	div = {n}
	prime = []
	x = n
	for i in range(2, int(sqrt(n) + 1)):
		if n % i == 0:
			div.add(i)
			div.add(n // i)
		if x % i == 0:
			prime.append(i)
			while x % i == 0:
				x = x // i
	if x != 1:
		prime.append(x)
	if len(prime) == 1:
		print(' '.join(map(str, div)))
		print(0)
		return
	if len(prime) == 2:
		if n == prime[0] * prime[1]:
			res = [prime[0], n, prime[1]]
			print(' '.join(map(str, res)))
			print(1)
			return
		else:
			res = [prime[0], n, prime[1]]
			div -= set(res)
			res += div
			print(' '.join(map(str, res)))
			print(0)
			return
	res = []
	last = prime[0] * prime[-1]
	div.remove(last)
	p = prime[0]
	for q in prime[1:]:
		res.append(p)
		div.remove(p)
		div.remove(p * q)
		pvals = [d for d in div if d % p == 0]
		div -= set(pvals)
		res += pvals
		res.append(p * q)
		p = q
	res.append(p)
	res.append(last)
	print(' '.join(map(str, res)))
	print(0)

def main():
	t = int(inputi())
	for _ in range(t):
		solve()
main()


import math

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

def finput():
	return float(input())

def linput():
	return [int(_) for _ in input().split()]

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
T = iinput()
for _ in range(T):
	n = iinput()
	s = int(math.sqrt(n))
	divs = []
	cons = []
	for i in range(2, s + 1):
		if n % i == 0:
			divs.append(i)
			if i * i != n:
				divs.append(n // i)
	divs.sort()
	cons.append(n)
	ans = 0
	while len(divs):
		flag = False
		for div in divs:
			if gcd(div, cons[-1]) != 1:
				cons.append(div)
				divs.remove(div)
				flag = True
				break
		if flag is False:
			cons.append(divs[0])
			divs.pop(0)
			ans += 1
	print(*cons)
	print(ans)


from math import sqrt, gcd

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

def sqr(n):
	l1 = []
	pa = set()
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			z1 = i
			z2 = n // i
			if z1 != z2:
				l1.append(z1)
				l1.append(z2)
			else:
				l1.append(z1)
	return l1
t = int(input())
n = 45
from collections import defaultdict
for _ in range(t):
	n = int(input())
	l1 = sqr(n)
	l2 = primeFactors(n)
	ans = 0
	l2.sort()
	hash = defaultdict(set)
	done = set()
	pro = []
	for i in range(len(l2) - 1):
		pro.append([l2[i], l2[i] * l2[i + 1]])
	for i in l2:
		for j in l1:
			if j % i == 0 and j not in done and (i != j):
				done.add(j)
				hash[i].add(j)
	l3 = []
	for (a, i) in pro:
		for j in hash[a]:
			if j % i == 0:
				hash[a].remove(j)
				l3.append(j)
				break
	s = []
	cnt = 0
	for i in range(len(l2)):
		s.append(l2[i])
		for j in hash[l2[i]]:
			s.append(j)
		if cnt < len(l3):
			s.append(l3[cnt])
			cnt += 1
	s += [n]
	for i in range(len(s) - 1):
		if gcd(s[i], s[i + 1]) == 1:
			ans += 1
	print(*s)
	print(ans)


import sys
input = sys.stdin.readline
import math

def yaku(x):
	xr = math.ceil(math.sqrt(x))
	LIST = []
	for i in range(1, xr + 1):
		if x % i == 0:
			LIST.append(i)
			LIST.append(x // i)
	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 (sorted(set(LIST)), sorted(set(FACT)))
t = int(input())
for tests in range(t):
	n = int(input())
	(L, SS) = yaku(n)
	USE = [0] * len(L)
	USE[0] = 1
	USE[-1] = 1
	ANS = [n]
	for i in range(len(SS) - 1):
		NEXT = SS[i] * SS[i + 1]
		ANSX = []
		for j in range(len(L)):
			if L[j] == NEXT:
				USE[j] = 1
			if USE[j] == 0 and L[j] % SS[i] == 0:
				USE[j] = 1
				ANSX.append(L[j])
		if NEXT != n:
			ANSX.append(NEXT)
		ANS += ANSX
	re = SS[-1]
	res = re
	while n % re == 0 and n != re:
		ANS.append(re)
		re *= res
	SC = 0
	for i in range(len(ANS)):
		if math.gcd(ANS[i], ANS[i - 1]) == 1:
			SC += 1
	print(*ANS)
	print(SC)


from sys import stdin, stdout

class Input:

	def __init__(self):
		self.lines = stdin.read().splitlines()
		self.idx = 0

	def line(self):
		try:
			return self.lines[self.idx]
		finally:
			self.idx += 1

	def array(self, sep=' ', cast=int):
		return list(map(cast, self.line().split(sep=sep)))

	def known_tests(self):
		(num_of_cases,) = self.array()
		for case in range(num_of_cases):
			yield self

	def unknown_tests(self):
		while self.idx < len(self.lines):
			yield self

class Problem:

	def __init__(self):
		self.oo = float('inf')
		self.primes = self.primes()

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

	def modpow(self, a, n, m):
		ans = 1
		while n:
			if n & 1:
				ans = ans * a % m
			n >>= 1
			a = a * a % m
		return ans

	def primes(self, n=10 ** 5 + 5):
		sieve = [i > 1 for i in range(n)]
		i = 2
		while i * i < n:
			if sieve[i]:
				for j in range(2 * i, n, i):
					sieve[j] = False
			i += 1
		primes = []
		for i in range(n):
			if sieve[i]:
				primes.append(i)
		return primes

	def solve(self, n):
		N = n
		f = []
		for p in self.primes:
			if p * p > n:
				break
			if n % p == 0:
				r = 0
				while n % p == 0:
					n //= p
					r += 1
				f.append((p, r))
			p += 1
		if n > 1:
			f.append((n, 1))
		d = [1]
		e = [0, 1]
		for (p, r) in f:
			q = 1
			l = e[-1]
			for i in range(r):
				q *= p
				for j in range(l):
					d.append(d[j] * q)
			e.append(len(d))
		for i in range(len(e) - 1):
			le = e[i]
			ri = e[i + 1]
			d[le:ri] = d[le:ri][::-1]
		if len(d) > 1:
			(d[-1], d[-2]) = (d[-2], d[-1])
		print(*d[1:])
		count = 0
		if len(f) == 2 and len(d) == 4:
			count += 1
		print(count)
try:
	p = Problem()
	for tc in Input().known_tests():
		p.solve(*tc.array())
except Exception as e:
	import traceback
	traceback.print_exc(file=stdout)


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

def factorise(n, P=None):
	f = {}
	if P is None:
		P = primes(int(n ** 0.5))
	for p in P:
		if p * p > n:
			break
		r = 0
		while n % p == 0:
			n //= p
			r += 1
		if r > 0:
			f[p] = r
	if n > 1:
		f[n] = 1
	return f
t = int(input())
V = [int(input()) for _ in range(t)]
P = primes(int(max(V) ** 0.5))
for n in V:
	f = factorise(n, P)
	Q = list(f)
	v = [1]
	D = []
	for i in range(len(Q)):
		p = Q[i]
		w = [x * p ** k for x in v for k in range(1, f[p] + 1)]
		v += w
		if i == 0:
			D += w
		else:
			pq = p * Q[i - 1]
			D += [pq] + [d for d in w if d != pq]
	print(' '.join((str(d) for d in D)))
	print(1 if tuple(f.values()) == (1, 1) else 0)


import os
import sys
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')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from collections import Counter

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small
for _ in range(int(input()) if True else 1):
	n = int(input())
	factors = distinct_factors(n)[1:]
	prime = set([k for k in prime_factors(n)])
	if len(prime) == 1:
		print(*factors)
		print(0)
		continue
	a = []
	found = False
	while 1:
		if not found:
			for factor in factors:
				if factor in prime:
					a += [factor]
			exists = False
			i = 0
			used = set()
			while i < len(a):
				if a[i] in prime and a[(i + 1) % len(a)] in prime and (a[i] * a[(i + 1) % len(a)] not in used):
					a.insert(i + 1, a[i] * a[(i + 1) % len(a)])
					used.add(a[i + 1])
				i += 1
			sa = set(a)
			factors = [k for k in factors if k not in sa]
			found = True
		pos = False
		i = len(a) - 1
		while i >= 0 and factors:
			if min(gcd(a[i], factors[-1]), gcd(a[(i + 1) % len(a)], factors[-1])) != 1:
				a.insert(i + 1, factors.pop())
				pos = True
				break
			i -= 1
		if not pos or not factors:
			break
	print(*a + factors)
	print(1 if factors or (len(prime) == 2 and prod(list(prime), 10 ** 12) == n) else 0)


import random
from math import gcd, sqrt, floor, ceil

def solve_1(n):
	d = divisors(n)
	order = [0] * len(d)
	moves = [999999999] * 1
	mark = [False] * len(d)
	permutation(d, [0] * len(d), 0, moves, mark, order)
	if gcd(order[0], order[-1]) == 1:
		moves[0] += 1
	return (order, moves[0])

def permutation(d, p, pos, moves, mark, order):
	if pos == len(d):
		m = 0
		for i in range(len(p) - 1):
			if gcd(p[i], p[i + 1]) == 1:
				m += 1
		if m < moves[0]:
			moves[0] = m
			for i in range(len(p)):
				order[i] = p[i]
		return
	for i in range(len(d)):
		if not mark[i]:
			mark[i] = True
			p[pos] = d[i]
			permutation(d, p, pos + 1, moves, mark, order)
			mark[i] = False
	return

def divisors(n):
	d = []
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			d.append(i)
			if i * i != n:
				d.append(n // i)
	d.append(n)
	merge_sort(d, 0, len(d) - 1, [0] * len(d))
	return d

def merge_sort(A, l, r, B):
	if l < r:
		m = (r + l) // 2
		merge_sort(A, l, m, B)
		merge_sort(A, m + 1, r, B)
		merge(A, l, r, B)
	return

def merge(A, l, r, B):
	m = (r + l) // 2
	(k, p, q) = (l, l, m + 1)
	while p <= m and q <= r:
		if A[p] < A[q]:
			B[k] = A[p]
			p += 1
		else:
			B[k] = A[q]
			q += 1
		k += 1
	while p <= m:
		B[k] = A[p]
		k += 1
		p += 1
	while q <= r:
		B[k] = A[q]
		k += 1
		q += 1
	for i in range(l, r + 1):
		A[i] = B[i]
	return

def solve_2(n):
	d = divisors(n)
	moves = 0
	order = sort(d)
	if gcd(order[0], order[-1]) == 1:
		moves += 1
	return (order, moves)

def sort(divs):
	order = []
	order.append(divs[0])
	count = len(divs)
	divs.remove(divs[0])
	while len(order) < count:
		for d in divs:
			if gcd(d, order[-1]) != 1:
				order.append(d)
				divs.remove(d)
				break
	return order

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		(order, moves) = solve_2(n)
		print(' '.join((str(j) for j in order)))
		print(moves)
	return

def random_cases():
	n = random.randint(2, 50)
	print('Case: \n' + 'n = ' + str(n))
	(order, moves) = solve_2(n)
	print(' '.join((str(i) for i in order)))
	print(moves)
	return

def tester():
	for i in range(1, 20):
		n = random.randint(4, 50)
		(order_1, moves_1) = solve_1(n)
		(order_2, moves_2) = solve_2(n)
		print('Case ' + str(i) + ':\n' + 'n = ' + str(n))
		print('solucion fuerza bruta : \n' + ' '.join((str(i) for i in order_1)) + '\n' + str(moves_1))
		print('solucion eficiente : \n' + ' '.join((str(i) for i in order_2)) + '\n' + str(moves_2))
		for i in range(min(len(order_1), len(order_2))):
			if order_1[i] != order_2[i] or len(order_1) != len(order_2) or moves_1 != moves_2:
				print('Wrong Answer\n')
				return
		print('Accepted\n')
	return
main()


import sys, math
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

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())
from functools import reduce

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

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

def solve():
	N = getInt()
	facs = prime_factors(N)
	if len(facs) == 2 and facs[0][1] == 1 and (facs[1][1] == 1):
		print(facs[0][0], facs[1][0], facs[0][0] * facs[1][0])
		print(1)
		return
	prime_facs = [f[0] for f in facs]
	facs2 = factors(N)
	facs2.remove(1)
	for p in prime_facs:
		facs2.remove(p)
	to_add = []
	lenP = len(prime_facs)
	if lenP > 2:
		for j in range(lenP):
			y = prime_facs[j] * prime_facs[(j + 1) % lenP]
			to_add.append(y)
			facs2.remove(y)
		ans = []
		for j in range(lenP):
			ans.append(prime_facs[j])
			ans.append(to_add[j])
	elif lenP == 1:
		ans = [prime_facs[0]]
	else:
		(p0, p1) = prime_facs
		facs2.remove(p0 * p1)
		facs2.remove(N)
		ans = [p0, N, p1, p0 * p1]
	for ff in facs2:
		for p in prime_facs:
			if ff % p == 0:
				prime = p
				break
		x = ans.index(prime)
		ans.insert(x + 1, ff)
	assert len(ans) == len(factors(N)) - 1
	print(*ans)
	print(0)
	return
T = getInt()
for t in range(T):
	solve()


t = int(input())
from math import sqrt, floor
for i in range(t):
	N = int(input())
	n = N
	p = {}
	for k in range(2, floor(sqrt(n)) + 1):
		if N % k == 0:
			cnt = 0
			while N % k == 0:
				cnt += 1
				N //= k
			p[k] = cnt
	if N != 1:
		p[N] = 1
	if len(p) == 1:
		k = tuple(p.keys())[0]
		print(*[k ** i for i in range(1, p[k] + 1)])
		print(0)
	elif len(p) == 2:
		(a, b) = p.keys()
		if p[a] == p[b] == 1:
			print(a, b, n)
			print(1)
		else:
			if p[a] == 1:
				(a, b) = (b, a)
			A = [n] + [a ** i for i in range(1, p[a] + 1)] + [a ** i * b ** j for i in range(1, p[a] + 1) for j in range(1, p[b] + 1) if i != p[a] or j != p[b]] + [b]
			print(*A)
			print(0)
	else:
		ites = sorted(p.items(), key=lambda x: x[1])
		if ites[-1][1] == 1:
			(a, b, c, *ites) = ites
			(a, b, c) = (a[0], b[0], c[0])
			A = [a * b * c, 1, a, a * b, b, b * c, c, c * a]
		else:
			(ka, va) = ites.pop()
			A = [ka, 1] + [ka ** i for i in range(2, va + 1)]
		for (k, v) in ites:
			A += [a * k ** i for i in range(1, v + 1) for a in A]
		A.reverse()
		x = A.pop()
		A.pop()
		print(*A, x)
		print(0)


import sys
input = sys.stdin.readline
fact = []
output = []

def add_new(i, parent, exponents=None):
	if parent:
		exponents = [0] * len(fact)
	if i == len(fact):
		curr = 1
		for i in range(len(exponents)):
			curr *= fact[i][0] ** exponents[i]
		output.append(curr)
		return
	for exp in range(parent, fact[i][1] + 1):
		exponents[i] = exp
		add_new(i + 1, 0, exponents)

def prog():
	global fact
	global output
	for _ in range(int(input())):
		ans = 0
		output = []
		fact = []
		n = int(input())
		a = n
		for i in range(2, int(a ** 0.5) + 1):
			if n % i == 0:
				curr = 0
				while n % i == 0:
					n //= i
					curr += 1
				fact.append([i, curr])
		if n * n > a:
			fact.append([n, 1])
			if len(fact) == 2 and fact[0][1] + fact[1][1] == 2:
				ans = 1
		for i in range(len(fact)):
			add_new(i, 1)
		for i in range(len(output)):
			if output[i] % fact[-1][0] == 0:
				new = output[i]
				del output[i]
				output = [new] + output
				break
		print(*output)
		print(ans)
prog()


import math

def find(n):
	ans = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			power = 0
			while n % i == 0:
				power += 1
				n //= i
			ans.append((i, power))
	if n != 1:
		ans.append((n, 1))
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	facts = find(n)
	output = []

	def back(i, parent, expo=None):
		if parent:
			expo = [0] * len(facts)
		if i == len(facts):
			curr = 1
			for (i, x) in enumerate(expo):
				curr *= facts[i][0] ** x
			output.append(curr)
			return
		else:
			for exp in range(parent, facts[i][1] + 1):
				expo[i] = exp
				back(i + 1, 0, expo)
	for i in range(len(facts)):
		back(i, 1)
	for i in range(len(output)):
		if output[i] % facts[-1][0] == 0:
			new = output[i]
			del output[i]
			output = [new] + output
			break
	print(*output)
	if len(output) == 3 and len(facts) == 2:
		print(1)
	else:
		print(0)


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

def divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	divisors.sort()
	return divisors

def prime_factorize(n, unique=False):
	b = 2
	fct = []
	while b * b <= n:
		while n % b == 0:
			n //= b
			fct.append(b)
		b = b + 1
	if n > 1:
		fct.append(n)
	if unique:
		return set(fct)
	else:
		return fct
t = int(input())
for _ in range(t):
	n = int(input())
	div = divisors(n)[1:]
	prime = prime_factorize(n)
	p_cnt = Counter(prime)
	p_key = list(p_cnt.keys())
	if len(prime) == 2 and len(p_cnt) == 2:
		print(*div)
		print(1)
		continue
	if len(prime) > 2 and len(p_cnt) == 2:
		groupA = []
		groupB = []
		groupC = []
		p1 = p_key[0]
		p2 = p_key[1]
		for item in div:
			if item % p1 == 0 and item % p2 == 0:
				groupC.append(item)
			elif item % p1 == 0:
				groupA.append(item)
			else:
				groupB.append(item)
		ans = groupA + [groupC[0]] + groupB + groupC[1:]
		print(*ans)
		print(0)
		continue
	if len(p_cnt) == 1:
		print(*div)
		print(0)
		continue
	single = dict()
	adj_pair = set()
	for (p1, p2) in zip(p_key, p_key[1:]):
		adj_pair.add(p1 * p2)
	adj_pair.add(p_key[0] * p_key[-1])
	for key in p_cnt.keys():
		single[key] = []
	for d in div:
		if d in adj_pair:
			continue
		for key in p_key:
			if d % key == 0:
				single[key].append(d)
				break
	ans = []
	for (p1, p2) in zip(p_key, p_key[1:]):
		ans += single[p1] + [p1 * p2]
	ans += single[p_key[-1]]
	ans += [p_key[0] * p_key[-1]]
	print(*ans)
	print(0)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from math import sqrt, ceil
for _ in range(int(input())):
	n = int(input())
	factors = [n]
	primeFactors = []
	for i in range(2, ceil(sqrt(n)) + 2):
		if n % i == 0 and factors[-1] != i:
			factors.append(i)
			if i != n // i:
				factors.append(n // i)
	isPrime = [True] * len(factors)
	factors.sort()
	for i in range(len(factors)):
		for j in range(i):
			if factors[i] % factors[j] == 0:
				isPrime[i] = False
				break
	for i in range(len(factors)):
		if isPrime[i]:
			primeFactors.append(factors[i])
	if len(primeFactors) <= 1:
		print(' '.join(map(str, factors)))
		print(0)
	elif len(factors) == 3 and factors[1] % factors[0] != 0:
		print(' '.join(map(str, factors)))
		print(1)
	elif len(primeFactors) == 2:
		a = primeFactors[0]
		b = primeFactors[1]
		ans = [a * b]
		i = 1
		while n % a ** i == 0:
			ans.append(a ** i)
			i += 1
		for elem in factors:
			if elem % a == 0 and elem % b == 0 and (elem != a * b):
				ans.append(elem)
		i = 1
		while n % b ** i == 0:
			ans.append(b ** i)
			i += 1
		print(' '.join(map(str, ans)))
		print(0)
	else:
		isCovered = [False] * len(factors)
		ans = []
		for i in range(len(primeFactors)):
			a = primeFactors[i]
			ans.append(a)
			for j in range(len(factors)):
				elem = factors[j]
				if elem % a == 0 and elem != a and (elem != a * primeFactors[(i + 1) % len(primeFactors)]) and (elem != a * primeFactors[i - 1]) and (not isCovered[j]):
					ans.append(elem)
					isCovered[j] = True
			ans.append(a * primeFactors[(i + 1) % len(primeFactors)])
		print(' '.join(map(str, ans)))
		print(0)


from sys import stdin, stdout
import math
import bisect

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

def solve(n):
	dv = [n]
	x = 2
	while x * x <= n:
		if n % x == 0:
			dv.append(x)
			if x != n // x:
				dv.append(n // x)
		x += 1
	dv = sorted(dv)
	ans = [0] * len(dv)
	(ans[0], ans[-1]) = (dv[0], dv[-1])
	seen = {dv[0], dv[-1]}
	cur_prime = dv[0]
	min_prime = dv[0]
	while len(seen) < len(dv):
		for x in dv:
			if x in seen:
				continue
			if min_prime == -1:
				min_prime = x
			if cur_prime == -1:
				if ans[len(seen) - 2] % x == 0:
					cur_prime = x
					ans[len(seen) - 1] = x
					seen.add(x)
			elif x % cur_prime == 0:
				ans[len(seen) - 1] = x
				seen.add(x)
		if cur_prime == -1:
			cur_prime = min_prime
		else:
			cur_prime = -1
		min_prime = -1
	cnt = 0
	for i in range(1, len(ans)):
		if gcd(ans[i], ans[i - 1]) == 1:
			cnt += 1
	print(' '.join(map(str, ans)))
	print(cnt)
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	solve(n)


import io, os
from random import randint
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def quickMulMod(a, b, m):
	ret = 0
	while b:
		if b & 1:
			ret = (a + ret) % m
		b //= 2
		a = (a + a) % m
	return ret

def quickPowMod(a, b, m):
	ret = 1
	while b:
		if b & 1:
			ret = quickMulMod(ret, a, m)
		b //= 2
		a = quickMulMod(a, a, m)
	return ret

def isPrime(n, t=5):
	t = min(n - 3, t)
	if n < 2:
		return False
	if n == 2:
		return True
	d = n - 1
	r = 0
	while d % 2 == 0:
		r += 1
		d //= 2
	tested = set()
	for i in range(t):
		a = randint(2, n - 2)
		while a in tested:
			a = randint(2, n - 2)
		tested.add(a)
		x = quickPowMod(a, d, n)
		if x == 1 or x == n - 1:
			continue
		for j in range(r - 1):
			x = quickMulMod(x, x, n)
			if x == n - 1:
				break
		else:
			return False
	return True

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

def decomp(n):
	if n == 1:
		return []
	if isPrime(n):
		return [n]
	fact = 1
	cycle_size = 2
	x = x_fixed = 2
	c = randint(1, n)
	while fact == 1:
		for i in range(cycle_size):
			if fact > 1:
				break
			x = (x * x + c) % n
			if x == x_fixed:
				c = randint(1, n)
				continue
			fact = gcd(x - x_fixed, n)
		cycle_size *= 2
		x_fixed = x
	return decomp(fact) + decomp(n // fact)

def allDivisions(n):
	P = decomp(n)
	P.sort()
	primes = [P[0]]
	counts = [0]
	for p in P:
		if p == primes[-1]:
			counts[-1] += 1
		else:
			primes.append(p)
			counts.append(1)
	k = len(primes)
	m = 1
	for c in counts:
		m *= c + 1
	l = m - 1
	ans = [0] * (l + 1)
	ans[0] = 1
	j = 1
	for i in range(k - 1, -1, -1):
		multis = [primes[i] ** _ for _ in range(1, counts[i] + 1)]
		for a in ans[:j]:
			for m in multis:
				ans[j] = a * m
				j += 1
	return ans[1:]

def NeiborNoCoPrime(n):
	P = decomp(n)
	P.sort()
	primes = [P[0]]
	counts = [0]
	for p in P:
		if p == primes[-1]:
			counts[-1] += 1
		else:
			primes.append(p)
			counts.append(1)
	k = len(primes)
	m = 1
	for c in counts:
		m *= c + 1
	l = m - 1
	A = [0] * (l + 1)
	A[0] = 1
	j = 1
	steps = [0] * k
	for i in range(k - 1, -1, -1):
		multis = [primes[i] ** _ for _ in range(1, counts[i] + 1)]
		steps[i] = j * len(multis)
		for a in A[:j]:
			for m in multis:
				A[j] = a * m
				j += 1
	B = [0] * l
	indB = 0
	startA = l + 1
	for i in range(k):
		step = steps[i]
		startA -= step
		indA = startA
		for s in range(step):
			B[indB] = A[indA]
			indB += 1
			indA += 1
	if k == 1:
		print(' '.join((str(num) for num in B)))
		print(0)
		return
	if k == 2:
		if primes[0] * primes[1] == n:
			print(' '.join((str(num) for num in B)))
			print(1)
			return
	aim = primes[0] * primes[-1]
	for i in range(l):
		if B[i] == aim:
			(B[0], B[i]) = (B[i], B[0])
	print(' '.join((str(num) for num in B)))
	print(0)
	return

def f():
	n = int(input())
	NeiborNoCoPrime(n)
for t in range(int(input())):
	f()


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi
from collections import deque, defaultdict
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
lcm = lambda x, y: x * y // gcd(x, y)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	a = []
	ln = 0
	if n % 2 == 0:
		if n // 2 != 2:
			a.extend([2, n // 2])
			ln += 2
		else:
			a.append(2)
			ln += 1
	for i in range(3, int(sqrt(n)) + 1):
		if n % i == 0:
			if n // i == i:
				a.append(i)
				ln += 1
			else:
				a.extend([i, n // i])
				ln += 2
	a.sort()
	if ln <= 2:
		if gcd(a[0], a[-1]) != 1:
			print(*a, n)
			print(0)
		else:
			print(a[0], a[1], n)
			print(1)
		continue
	p = n
	fact = []
	lm = int(sqrt(n)) + 1
	if p % 2 == 0:
		fact += (2,)
		while p % 2 == 0:
			p >>= 1
	j = 3
	while 1:
		if j > lm or j > p:
			break
		if p % j == 0:
			fact += (j,)
			while p % j == 0:
				p //= j
		j += 2
	if p != 1:
		fact += (p,)
	d = {i: [] for i in fact}
	for i in range(ln):
		for el in fact:
			if a[i] % el == 0:
				d[el].append(a[i])
				break
	ans = []
	for i in range(1, len(fact)):
		d[fact[i - 1]].remove(fact[i] * fact[i - 1])
		ans.extend(d[fact[i - 1]])
		ans.append(fact[i] * fact[i - 1])
	ans.extend(d[fact[-1]])
	ans.append(n)
	print(*ans)
	print(0)


from sys import stdin
input = stdin.readline
q = int(input())
for _ in range(q):
	n = int(input())
	pier = []
	i = 2
	nn = n
	while True:
		if nn % i == 0:
			pier.append(i)
			nn //= i
		else:
			i += 1
		if i ** 2 > n:
			break
	if nn != 1:
		pier.append(nn)
	pier_unique = list(set(pier))
	dzielniki = [1]
	for p in pier_unique:
		pot = p
		addition = []
		while n % pot == 0:
			addition1 = [d * pot for d in dzielniki]
			addition += addition1
			pot *= p
		dzielniki += addition
	dzielniki = dzielniki[1:]
	k = len(pier_unique)
	if k == 1:
		print(*dzielniki)
		print(0)
	elif k >= 3:
		dzielniki = set(dzielniki)
		odp = []
		for i in range(k):
			dzielniki.remove(pier_unique[i - 1] * pier_unique[i])
		for i in range(k):
			odp.append(pier_unique[i - 1] * pier_unique[i])
			to_rem = []
			for dz in dzielniki:
				if dz % pier_unique[i] == 0:
					to_rem.append(dz)
					odp.append(dz)
			for to in to_rem:
				dzielniki.remove(to)
		print(*odp)
		print(0)
	else:
		p = pier_unique[0]
		q = pier_unique[1]
		if n == p * q:
			print(p, q, p * q)
			print(1)
		else:
			test = p ** 2
			if n % test != 0:
				(p, q) = (q, p)
			dzielniki = set(dzielniki)
			dzielniki.remove(p * q)
			dzielniki.remove(p * p * q)
			odp = [p * q]
			to_rem = []
			for dzu in dzielniki:
				if dzu % p == 0:
					to_rem.append(dzu)
					odp.append(dzu)
			for tu in to_rem:
				dzielniki.remove(tu)
			odp.append(p * p * q)
			for dzu in dzielniki:
				odp.append(dzu)
			print(*odp)
			print(0)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

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

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
mod = 998244353
INF = float('inf')
for t in range(int(data())):
	n = int(data())
	ans = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			ans.append(i)
			n1 = n // i
			for j in range(i, int(n1 ** 0.5) + 1):
				if n1 % j == 0:
					ans.append(j * i)
					if j * j != n1:
						ans.append(n1 // j * i)
			if n != i:
				ans.append(n)
			while n % i == 0:
				n //= i
	if n != 1:
		ans.append(n)
	for i in range(len(ans)):
		if ans[i] % ans[0] == ans[i] % ans[-1] == 0:
			ans.append(ans.pop(i))
			break
	outl(ans)
	if len(ans) == 3 and math.gcd(ans[0], ans[1]) == 1:
		out(1)
	else:
		out(0)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += i % 2 + (3 if i % 3 == 1 else 1)
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(pf):
	ret = [1]
	for p in pf:
		ret_prev = ret
		ret = []
		for i in range(pf[p] + 1):
			for r in ret_prev:
				ret.append(r * p ** i)
	return sorted(ret)
T = int(input())
for _ in range(T):
	N = int(input())
	pf = primeFactor(N)
	dv = divisors(pf)
	if len(pf) == 2 and len(dv) == 4:
		print(*dv[1:])
		print(1)
		continue
	if len(pf) == 1:
		print(*dv[1:])
		print(0)
		continue
	lpf = list(pf)
	X = [[] for _ in range(len(pf))]
	S = {1}
	if len(lpf) == 2:
		X[0].append(lpf[0] * lpf[1])
		X[1].append(N)
		S.add(lpf[0] * lpf[1])
		S.add(N)
		for (i, p) in enumerate(lpf):
			for j in range(1, pf[p] + 1):
				X[i].append(p ** j)
				S.add(p ** j)
	else:
		for (i, p) in enumerate(lpf):
			X[i].append(lpf[i - 1] * p)
			S.add(lpf[i - 1] * p)
			for j in range(1, pf[p] + 1):
				X[i].append(p ** j)
				S.add(p ** j)
	for a in dv:
		if a not in S:
			for (i, p) in enumerate(lpf):
				if a % p == 0:
					X[i].append(a)
					break
	ANS = []
	for x in X:
		for y in x:
			ANS.append(y)
	print(*ANS)
	print(0)


import sys
import math
input = sys.stdin.readline

def get_simple_divisors(n):
	ans = []
	power = []
	d = 2
	while d <= math.sqrt(n):
		if n % d == 0:
			x = 0
			while n % d == 0:
				n //= d
				x += 1
			ans.append(d)
			power.append(x)
		else:
			d += 1
	if n != 1:
		ans.append(n)
		power.append(1)
	return (ans, power)

def build_divisors(simple, power, N):
	divisors = []

	def go(index, value):
		if index == len(simple):
			if value != N and value != 1:
				divisors.append(value)
			return
		for i in range(power[index] + 1):
			go(index + 1, value * simple[index] ** i)
	go(index=0, value=1)
	return divisors
T = int(input())
for t in range(T):
	N = int(input())
	(simple, power) = get_simple_divisors(N)
	groups = [[] for s in simple]
	divisors = build_divisors(simple, power, N)
	for div in divisors:
		for (i, s) in enumerate(simple):
			if div % s == 0:
				groups[i].append(div)
				break
	if len(simple) == 1:
		divisors.append(N)
		print(' '.join(map(str, divisors)))
		print(0)
		continue
	if len(simple) == 2 and simple[0] * simple[1] == N:
		divisors.append(N)
		print(' '.join(map(str, divisors)))
		print(1)
		continue
	solution = []
	for i in range(len(simple)):
		joints = set()
		if i > 0:
			joints.add(simple[i - 1] * simple[i])
		joints.add(simple[(i + 1) % len(simple)] * simple[i])
		for div in groups[i]:
			if div not in joints:
				solution.append(div)
		if i != len(simple) - 1:
			solution.append(simple[i] * simple[i + 1])
	solution.append(N)
	print(' '.join(map(str, solution)))
	print(0)


import sys
input = sys.stdin.readline
t = int(input())
A = [int(input()) for i in range(t)]
l = 2 * 10 ** 5 + 10

def yaku(K, V, YANS, s, now, maxs):
	if s == len(K):
		YANS.append([now, maxs])
	else:
		vv = 1
		for i in range(V[s] + 1):
			if i > 0:
				maxs = s
			yaku(K, V, YANS, s + 1, now * vv, maxs)
			vv *= K[s]
for ii in range(t):
	n = A[ii]
	mn = n
	D = {}
	ans = 0
	ANS = []
	di = 2
	sqrtn = int(n ** 0.5) + 10
	while n > 1 and di < sqrtn:
		while n % di == 0:
			n //= di
			try:
				D[di] += 1
			except:
				D[di] = 1
		di += 1
	if n != 1:
		D[n] = 1
	K = list(D.keys())
	V = list(D.values())
	if len(K) == 1:
		aa = K[0]
		ANS.append(aa)
		for i in range(V[0] - 1):
			ANS.append(aa * ANS[-1])
		print(*ANS)
	elif len(K) == 2:
		if V.count(1) == len(V):
			ans = 1
			ANS = [K[0], K[1], K[0] * K[1]]
			print(*ANS)
		else:
			YANS = []
			yaku(K, V, YANS, 0, 1, -1)
			AA = [[], []]
			YANS.sort()
			SE = [K[0] * K[1], mn]
			for i in range(1, len(YANS)):
				if not YANS[i][0] in SE:
					AA[YANS[i][1]].append(YANS[i][0])
			for i in range(len(K)):
				print(SE[i], end=' ')
				if i != len(K) - 1:
					print(*AA[i], end=' ')
				else:
					print(*AA[i])
	else:
		YANS = []
		yaku(K, V, YANS, 0, 1, -1)
		AA = [[] for i in range(len(K))]
		YANS.sort()
		SE = [K[i] * K[i - 1] for i in range(len(K))]
		SF = SE[:]
		SF.sort()
		sfi = 0
		lsf = len(SF)
		for i in range(1, len(YANS)):
			if sfi >= lsf or YANS[i][0] != SF[sfi]:
				AA[YANS[i][1]].append(YANS[i][0])
			else:
				sfi += 1
		ANS = []
		for i in range(len(K)):
			print(SE[i], end=' ')
			if i != len(K) - 1:
				print(*AA[i], end=' ')
			else:
				print(*AA[i])
	print(ans)


def getPrimeFactorCounts(x):
	primeFactorCnts = []
	for i in range(2, int(x ** 0.5) + 1):
		cnt = 0
		while x % i == 0:
			cnt += 1
			x //= i
		if cnt > 0:
			primeFactorCnts.append((i, cnt))
	if x > 1:
		primeFactorCnts.append((x, 1))
	return primeFactorCnts

def getAllFactors(x):
	factors = []
	for i in range(1, int(x ** 0.5) + 1):
		if x % i == 0:
			factors.append(i)
			if x // i != i:
				factors.append(x // i)
	return factors
t = int(input())
for _ in range(t):
	n = int(input())
	primeFactors = [x[0] for x in getPrimeFactorCounts(n)]
	allFactors = set(getAllFactors(n))
	allFactors.remove(1)
	ans = []
	nMoves = 0
	for i in range(1, len(primeFactors) + 1):
		a = primeFactors[i - 1]
		if i < len(primeFactors):
			b = primeFactors[i]
		else:
			b = primeFactors[0]
		if a == b:
			ans.append(a)
			allFactors.remove(a)
			break
		else:
			if a * b in allFactors:
				ans.append(a * b)
				allFactors.remove(a * b)
			elif a * a * b in allFactors:
				ans.append(a * a * b)
				allFactors.remove(a * a * b)
			elif a * b * b in allFactors:
				ans.append(a * b * b)
				allFactors.remove(a * b * b)
			else:
				nMoves += 1
			ans.append(b)
			allFactors.remove(b)
	for x in allFactors:
		for i in range(len(ans)):
			if x % ans[i] == 0:
				break
		ans.insert(i + 1, x)
	s = ' '.join([str(x) for x in ans])
	print(s)
	print(nMoves)


import sys
input = sys.stdin.readline

def factrization_prime(number):
	factor = []
	div = 2
	while div * div <= number:
		div_cnt = 0
		while number % div == 0:
			div_cnt += 1
			number //= div
		if div_cnt != 0:
			factor.append((div, div_cnt))
		div += 1
	if number > 1:
		factor.append((number, 1))
	return factor

def ys(l, a, x):
	if dd == a:
		return
	(t, s) = l[a]
	ys(l, a + 1, x)
	for y in range(1, s + 1):
		x *= t
		Z.append(x)
		ys(l, a + 1, x)
(T,) = map(int, input().split())
for _ in range(T):
	(N,) = map(int, input().split())
	d = factrization_prime(N)
	if len(d) == 1:
		Y = []
		c = 1
		for i in range(d[0][1]):
			c *= d[0][0]
			Y.append(c)
		print(*Y)
		print(0)
		continue
	if len(d) == 2:
		if d[0][1] + d[1][1] == 2:
			print(d[0][0], d[1][0], N)
			print(1)
			continue
	Y = []
	dd = len(d)
	for i in range(dd):
		(a, b) = d[i]
		(ff, zz) = (a * d[i + 1 if i != dd - 1 else 0][0], a * d[-1][0])
		x = 1
		Z = []
		for j in range(1, b + 1):
			x *= a
			Z.append(x)
			ys(d, i + 1, x)
		if dd == 2:
			if i == 0:
				Y.append(N)
				for z in Z:
					if z == ff:
						continue
					if z == N:
						continue
					Y.append(z)
				Y.append(ff)
			else:
				for z in Z:
					Y.append(z)
		elif i == 0:
			Y.append(zz)
			for z in Z:
				if z == ff:
					continue
				if z == zz:
					continue
				Y.append(z)
			Y.append(ff)
		elif i != dd - 1:
			for z in Z:
				if z == ff:
					continue
				Y.append(z)
			Y.append(ff)
		else:
			for z in Z:
				Y.append(z)
	print(*Y)
	print(0)


import os
import sys
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()

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

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

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from math import ceil, floor, sqrt, pow
for i in range(N()):
	n = N()
	(nn, k) = (n, 2)
	(p, d) = ([], [i for i in range(2, int(sqrt(n)) + 1) if n % i == 0])
	d += [n // i for i in d]
	d = set(d)
	d.add(n)
	for i in d:
		if nn % i == 0:
			p.append(i)
			while nn % i == 0:
				nn //= i
	if len(p) == 1:
		print_list(d)
		print(0)
	elif len(p) == 2:
		if len(d) == 3:
			print_list(d)
			print(1)
		else:
			(a, b) = (p[0], p[1])
			res = [a * b, a]
			d -= {a * b, a, n}
			for i in d:
				if i % a == 0:
					res.append(i)
			res.append(n)
			for i in d:
				if i % a > 0:
					res.append(i)
			print_list(res)
			print(0)
	else:
		res = []
		s = 0
		pp = [p[i] * p[i - 1] for i in range(1, len(p))] + [p[0] * p[-1]]
		d -= set(pp)
		d -= set(p)
		for i in range(len(p)):
			k = p[i]
			for t in d:
				if t % k == 0:
					res.append(t)
			d -= set(res[s:])
			s = len(res)
			res.append(p[i])
			res.append(pp[i])
		print_list(res)
		print(0)