Problem: An agent called Cypher is decrypting a message, that contains a [composite number](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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 ≤ t ≤ 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 ≤ n ≤ 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 ⋅ 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.

Solution (in PYTHON3):

Solution:
import random                  #libreria_necesaria_para_generar_numeros_de_forma_aleatoria
from math import gcd, sqrt, floor, ceil           #librerias_ncesarias_para_realizar_los_calculos_necesarios


# __________________________________________________#
# brute force solution_____________________________#
def solve_1(n):
    d = divisors(n)           #lista_de_divisores_de_n
    order = [0] * len(d)      #ordenacion_final
    moves = [999999999] * 1   #cantidad_de_pares_coprimos_en_la_ordenacion_final
    mark = [False] * len(d)   #mascara_booleana_util_para_generar_permutaciones
    permutation(d, [0] * len(d), 0, moves, mark, order)   #generando_posibles_permutaciones

    if gcd(order[0], order[-1]) == 1:   #revisando_par_de_adyacentes_que_completan_el_circulo
        moves[0] += 1

    return order, moves[0]

def permutation(d, p, pos, moves, mark, order):    #algoritmo_para_generar_todas_permutaciones
    if pos == len(d):          #si_en_la_permutacion_estan_todos_los_divisores_no_se....
                               #agregan_mas_elementos_y_es_analizada
        m = 0
        for i in range(len(p) - 1):       #contando_cantidad_de_pares_coprimos_en_la_permutacion
            if gcd(p[i], p[i + 1]) == 1:
                m += 1
        if m < moves[0]:       #condicion_para_tener_en_la_ordenacion_final_la_permutacion
                               #de_menor_canridad_de_pares_coprimos
            moves[0] = m
            for i in range(len(p)):
                order[i] = p[i]
        #print(p)      #descomentar_para_imprimir_permutaciones
        return

    for i in range(len(d)):
        if not mark[i]:        #si_el_divisor_d[i]_no_esta_agregado_en_la_permutacion_entonces_se_agrega
            mark[i] = True     #se_marca_divisor_como_agregado
            p[pos] = d[i]      #se_agrega_divisor_a_la_permutacion
            permutation(d, p, pos + 1, moves, mark, order)  #llamado_recursivo
            mark[i] = False    #se_desmarca_divisor_como_agregado

    return

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

def merge_sort(A, l, r, B):    #algoritmo_de_ordenacion_mergesort
    if l < r:
        m = (r + l) // 2     #elemento_en_la_mitad_entre_l_y_r
        merge_sort(A, l, m, B)     #llamado_recursivo_para_ordenar_la_primera_mitad
        merge_sort(A, m + 1, r, B)    #llamado_recursivo_para_ordenar_la_segunda_mitad
        merge(A, l, r, B)     #mezcla_ordenada_de_ambas_mitades
    return

def merge(A, l, r, B):
    m = (r + l) // 2
    k, p, q = l, l, m + 1    #indice_en_el_array_mezclado/#indice_en_la_primera_mitad/#indice_en_la_segunda_mitad

    while (p <= m and q <= r):   #mientras_queden_elementos_sin_tomar_en_ambas_mitades
        if (A[p] < A[q]):
            B[k] = A[p]   #el_elemento_de_la_primera_mitad_es_menor
            p += 1
        else:
            B[k] = A[q]   #el_elemento_de_la_segunda_mitad_es_menor
            q += 1
        k += 1

    while (p <= m):  #no_quedan_elementos_por_tomar_en_la_segunda_mitad_pero_quedan_en_la_primera
        B[k] = A[p]
        k += 1
        p += 1

    while (q <= r):  #no_quedan_elementos_por_tomar_en_la_primera_mitad_pero_quedan_en_la_segunda
        B[k] = A[q]
        k += 1
        q += 1

    for i in range(l, r + 1):  #copiar_la_mezcla_en_A
        A[i] = B[i]

    return


# __________________________________________________#
# solution_________________________________________#
def solve_2(n):
    d = divisors(n)   #lista_de_divisores
    moves = 0         #cantidad_de_pares_coprimos

    order = sort(d)   #creando_ordenacion_final
    if(gcd(order[0], order[-1]) == 1):    #comprobando_par_adyacente_que_completa_el_circulo
        moves += 1

    return order, moves

def sort(divs):
    order = []     #ordenacion_final
    order.append(divs[0])   #agregando_primer_divisor
    count = len(divs)       #cantidad_de_divisores
    divs.remove(divs[0])    #eliminando_primer_divisor_de_la_lista_de_divisores

    while(len(order) < count):    #mientras_falten_divisores_por_agregar_a_order
        for d in divs:            #buscando_en_d_un_divisor_que_no_sea_coprimo_con_el_ultimo_que_se_agrego_a_order
            if  gcd(d , order[-1]) != 1:   #cuando_se_encuentra_se_agrega_a_order_y_se_elimina_de_d
                order.append(d)
                divs.remove(d)
                break    #ya_se_encontro_el_divisor_que_se_buscaba_entonces_se_rompe_el_ciclo
                         #Ahora_el_ultimo_divisor_en_order_es_el_que_se_agrego
    return order


# __________________________________________________#
# main_____________________________________________#
def main():
    t = int(input())    #cantidad_de_casos_prueba
    for i in range(t):    #por_cada_caso_prueba_se_ejecuta_la_solucion
        n = int(input())
        #order, moves = solve_1(n)     #solucion_fuerza_bruta
        order, moves = solve_2(n)      #solucion_eficiente
        print(' '.join(str(j) for j in order))    #imprimiendo_ordenacion_final
        print(moves)        #imprimiendo_cantidad_de_pares_coprimos
    return


# _________________________________________________#
# random cases tester______________________________#
def random_cases():
    n = random.randint(2, 50)     #valor_n_aleatorio
    print('Case: \n' + "n = " + str(n))
    #order, moves = solve_1(n)     #solucion_fuerza_bruta
    order, moves = solve_2(n)     #solucion_eficiente
    print(' '.join(str(i) for i in order))  #imprimiendo_ordenacion_final
    print(moves)     #imprimiendo_cantidad_de_pares_coprimos

    return


# __________________________________________________#
# tester___________________________________________#
def tester():
    for i in range(1, 20):               #cantidad_de_casos_que_se_desean_probar
        n = random. randint(4, 50)       #valor_n_aleatorio
        order_1, moves_1 = solve_1(n)       #solucion_fuerza_bruta
        order_2, moves_2 = solve_2(n)       #solucion_eficiente

        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))     #solucion_fuerza_bruta
        print('solucion eficiente : \n' + ' '.join(str(i) for i in order_2) + '\n' + str(moves_2))        #solucion_eficiente
        for i in range(min(len(order_1), len(order_2))):    #verificando_si_la_soluciones_coinciden
            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()             #entrada_de_casos_por_consola
#random_cases()    #casos_random
#tester()          #comprobar_solucion_eficiente_contra_solucion_fuerza_bruta