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.

Difficulty: interview

Starter code:

Solutions:
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]
    # print(pg)
    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)



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)
    # print("lpf =", lpf)
    
    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):
            # print("i, p, pf[p] =", i, p, pf[p])
            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
    # print("X =", X)
    ANS = []
    for x in X:
        for y in x:
            ANS.append(y)
    print(*ANS)
    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)


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 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
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 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)
    # print(l, l1)
    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
    # print(l, l1)
    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)
    # print(l, l1, d)

    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 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
            #p^2 dzieli n
            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)



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)
            else:
                if 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)

#for i in range(2, 50):
#    solve(i)


# prime power always 0
# two prime powers?
#
# == 1 prime factor
#   trivial
# == 2 prime factors
#   p^a q^b
#   if a + b > 2: then fine
#   p*q
#   (remaining with p)
#   p*p*q
#   (remaining with q)
# >= 3 prime factors is fine
#   what ordering?
#   p*q*r
#   (all left with p)
#   p*q
#   (all left with q)
#   q*r
#   (all left with r)

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 divisors are equal, print only one 
            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)


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)
        # print(facs)
        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)

        # elif len(facs) == 2:







def __starting_point():
    main()
__starting_point()

def gen(i, cur):
    nonlocal 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))