Problem: You are given an integer n (n > 1).

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

  * each a_i is strictly greater than 1; 
  * a_1 ⋅ a_2 ⋅ … ⋅ a_k = n (i. e. the product of this sequence is n); 
  * a_{i + 1} is divisible by a_i for each i from 1 to k-1; 
  * k is the maximum possible (i. e. the length of this sequence is the maximum possible). 



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

You have to answer t independent test cases.

Input

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

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

It is guaranteed that the sum of n does not exceed 10^{10} (∑ n ≤ 10^{10}).

Output

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

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

Example

Input


4
2
360
4999999937
4998207083


Output


1
2 
3
2 2 90 
1
4999999937 
1
4998207083 

Solution (in PYTHON):

Solution:
from __future__ import division, print_function
import bisect
import math
import heapq
import itertools
import sys
from collections import deque
from atexit import register
from collections import Counter
from functools import reduce
sys.setrecursionlimit(100000)
if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""

        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        def input(): return sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


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


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


def primeFactors(n):
    fact=[]

    # Print the number of two's that divide n
    while n % 2 == 0:
        fact.append(2)
        n = n // 2

    # n must be odd at this point
    # so a skip of 2 ( i = i + 2) can be used
    for i in range(3, int(math.sqrt(n))+1, 2):

        # while i divides n , print i ad divide n
        while n % i == 0:
            fact.append(i)
            n = n // i

    # Condition if n is a prime
    # number greater than 2
    if n > 2:
        fact.append(n)
    return fact

def transpose(l1, l2): 
  
    # iterate over list l1 to the length of an item  
    for i in range(len(l1[0])): 
        # print(i) 
        row =[] 
        for item in l1: 
            # appending to new list with values and index positions 
            # i contains index position and item contains values 
            row.append(item[i]) 
        l2.append(row) 
    return l2 
    
def main():
    for _ in range(int(input())):
        n = int(input())
        fact=primeFactors(n)

        d={}
        for i in fact:
            try:
                d[i]+=1
            except:
                d[i]=1
        freq=[]
        dig=[]
        for i in d:
            freq.append(d[i])
            dig.append(i)
        
        dig=[x for _,x in sorted(zip(freq,dig))]

        freq.sort()

        cell=[]
        fff=[]
        for i in range(len(freq)):
            temp=[]
            for j in range(freq[i]):
                temp.append(dig[i])
            for k in range(freq[-1]-len(temp)):
                temp.append(1)
            cell.append(temp)
        
        cell=(transpose(cell, []))
        print(freq[-1])
        for i in range(len(cell)):
            temp=1
            for j in range(len(cell[i])):
                temp*=cell[i][j]
            fff.append(temp)
        fff.sort()
        for i in fff:
            print(i,end=' ')
        print()

        

            
        


if __name__ == '__main__':
    sync_with_stdio(False)
    main()