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 JAVA):

Solution:
// Author : AMIT KUMAR BARMAN (gearman_0712)
import java.io.*;
import java.util.*;

public class ns{
    static final long modp =1000007;
    static long x_ec=1,y_ec=0,d_ec =1;
    static long maxi=0;
    static boolean v1 =false ,v2 = false;
    static InputReader in = new InputReader(System.in);
    static OutputStream outputStream = System.out;
    static OutputWriter out = new OutputWriter(outputStream);
    static class item {
        int a,b;
        item(int a ,int b)
        {this.a= a;
            this.b= b;

        }
    }
    static int[] sieve()
    {int ma= 1000005;
     

        boolean Assign[] = new boolean[ma];
        int smallp[] = new int[ma];
      
        for(int i=2;i<ma;i +=2)
         smallp[i]=2;
         for(int i=3;i<ma ;i +=2)
         {  if(!Assign[i])
            { smallp[i]=i;
               
             for(int j=i;(long)i*j<(long)ma ;j +=2)
             { if(!Assign[i*j])
                { smallp[i*j]=i;
                     Assign[i*j] = true;
                }
                 
             }
             
            }
         }
       
         return smallp;
        

    }
//     static long fact(int smallp[],int n)
//     { HashMap<Integer,Integer> map = new HashMap<>();
//         long h=n;
//         int u=0;
//         while(n!=1)
//          {  u= smallp[n];
//              if(!map.containsKey(u))
//              map.put(u,0);
//              map.put(u, map.get(u)+1);
//        n= n/u;
//         }
//         long i[]= new long[1];
//         i[0]=1;
//         out.println(map);
//         map.forEach((k,v) -> i[0] = (mulmod(i[0],(2*v*h +1)%modp, modp)));

// return i[0];

//     }

  
   
     public static void main (String args[]) throws IOException {
        int t = in.readInt();
        int smallp[] = sieve();
         while(t-->0)
         { long n = in.readLong();
  ArrayList<item> al = new ArrayList<>();
           long y=n;
           for(int i=2 ;(long)i*i<=n && y>0 ;i++)
           { if(smallp[i]==i && y%i==0)
            {   int c=0;
                while(y%i ==0 && y>0)
                { y /= i;
                  c++;
                }
               
              al.add(new item(i,c));

            }
           }
           int first =0;
           int sec =-1;
           for(int i= 0;i<al.size() ;i++)
           { item temp=al.get(i);
         if(temp.b>sec)
         { first = temp.a;
            sec = temp.b;

         }
           }
           long j=1;
           if(sec==-1)
           { out.println(1);
            out.println(n);
           }
          
           else
           { out.println(sec);
               for(int i=0;i<sec-1 ;i++)
           { out.print(first+" ");
           j*=first;
            
           }
           out.println(n/j);

           }
           

         }
       

          out.close();
}
    /*
    static Node lca(Node root,int x,int y)
    {if(root==null)
        return null;
        if(root.value>x &&root.value>y )
        return lca(root.left, x, y);
         if(root.value<x &&root.value<y )
        return lca(root.right, x, y);
    
        return root;
    }
    
    
    
    
    static Node common(Node root,int x,int y)
    {  if(root==null)
        return null;
        Node temp=null;
        if(root.value ==x)
        { v1= true;
            temp =new Node(x);
    
        }
        else if(root.value ==y)
        { v2= true;
            temp =new Node(y);
    
        }
      Node  lef =common(root.left, x, y);
     Node rig =common(root.right, x, y);
       if(temp!=null)
       return temp;
       if(lef ==null)
       return rig;
       if(rig==null)
       return lef;
       return root;
    }
    
    // static class Node {
    //     int value;
    //     Node left;
    //     Node right;
        
    //     Node(int value){
    //         this.value =value;
    //         right =null;
    //         left =null;
    //     }
    // }
    static Node insert(Node root,int v)
      { if(root==null)
        return new Node(v);
          if( v<=root.value)
          root.left =insert(root.left, v);
          else
          root.right =insert(root.right,v);
    
          return root;
    
        }
      
      static int minvalue(Node root)
        {
            while(root.left!=null)
              root =root.left;
              return root.value;
    
            
    
        }
 static int[] computeLPSArray(String patt)
  {   int m=  patt.length();
      int Lps[]= new int[m];
      int i=1 ,len=0;
      Lps[0]=0;
      while( i<m)
      { if(patt.charAt(i)==patt.charAt(len))
        { len++;
            Lps[i]=len;
           i++;
        }
        else 
        {  if(len!=0)
            {len =Lps[len-1];

            }
            else //len=0
             Lps[i++]=len;


        }



      }

    return Lps;

  }
        static Node delete(Node root ,int val)
     { if(root ==null)
        return root;
        if(val<root.value)
        root.left=delete(root.left, val);
       else if(val>root.value)
       root.right =delete(root.right,val);
       else {
       if(root.left==null)
         return root.right;
         else if(root.right==null)
         return root.left;
         root.value= minvalue(root.right);
         root.right =delete(root.right, root.value);
       
    
       }
       return root;
    
    
     }
     */
    /*
     static void inorder(Node root,OutputWriter out)
     { if(root!=null)
       {inorder(root.left ,out);
          out.print(root.value+" ");
          inorder(root.right, out);
    
       }
     }
     static void preorder(Node root ,OutputWriter out)
     { if(root!=null)
       { out.println(root.value+" ");
          preorder(root.left, out);
          preorder(root.right,out);
    
       }
    
     }
     static void postorder(Node root,OutputWriter out)
     { if(root!=null)
       { postorder(root.left, out);
           postorder(root.right ,out);
           out.print(root.value+" ");
       }
    
     }
     */
    // Input: Indices Range [0..size]
    // Invariant: A[l] <= key and A[r] > key 
    static long modExponential(long x,long n)
        {long result =1l;
            while(n>0l)
            { if(n%2==1)
                result =(x*result)%modp;
                x= (x*x)%modp;
             n=n/2;
            }
            return result;
        }
      /*
    static int GetRightPosition(int A[], int l, int r, int key) 
    { 
        int m; 
    
        while( r - l > 1 ) 
        { 
            m = l + (r - l)/2; 
    
            if( A[m] <= key ) 
                l = m; 
            else
                r = m; 
        } 
    
        return l; 
    } 
    
    // Input: Indices Range -1 to size-1
    // Invariant: A[r] >= key and A[l] > key 
    static int GetLeftPosition(int A[], int l, int r, int key) 
    { 
        int m; 
    
        while( r - l > 1 ) 
        { 
            m = l + (r - l)/2; 
    
            if( A[m] >= key ) 
                r = m; 
            else
                l = m; 
        } 
    
        return r; 
    } 
    
    */
    
    public static long gcd(long a,long b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    public static int gcd(int a,int b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    public static int abs(int a,int b)
    {
        return (int)Math.abs(a-b);
    }
    public static long abs(long a,long b)
    {
        return (long)Math.abs(a-b);
    }
    public static int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
    public static int min(int a,int b)
    {
        if(a>b)
            return b;
        else 
            return a;
    }
    public static long max(long a,long b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
    public static long min(long a,long b)
    {
        if(a>b)
            return b;
        else 
            return a;
    }
     
    /*
    void countsort(int arr[],int n,int place)
    {
            int i,freq[range]={0};         //range for integers is 10 as digits range from 0-9
            int output[n];
            for(i=0;i<n;i++)
                    freq[(arr[i]/place)%range]++;
            for(i=1;i<range;i++)
                    freq[i]+=freq[i-1];
            for(i=n-1;i>=0;i--)
            {
                    output[freq[(arr[i]/place)%range]-1]=arr[i];
                    freq[(arr[i]/place)%range]--;
            }
            for(i=0;i<n;i++)
                    arr[i]=output[i];
    }
    void radixsort(ll arr[],int n,int maxx)            //maxx is the maximum element in the array
    {
            int mul=1;
            while(maxx)
            {
                    countsort(arr,n,mul);
                    mul*=10;
                    maxx/=10;
            }
    }*/
    
    /* BufferedReader bf =new BufferedReader (new InputStreamReader(System.in));
            int t= Integer.parseInt(bf.readLine());
            StringBuffer gh =new StringBuffer("");
            StringTokenizer  tk=new StringTokenizer(bf.readLine());
            long a= Long.parseLong(tk.nextToken());
    */
    
    
    static class Pair implements Comparable<Pair>
    {
        int a,b;
        Pair (int a,int b)
        {
            this.a=a;
            this.b=b;
        }
     
        public int compareTo(Pair o) {
            
            if(this.a!=o.a)
            return -Integer.compare(this.a,o.a);
            else
                return Integer.compare(this.b, o.b);
            //return 0;
        }
        public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.a == a && p.b == b;
            }
            return false;
        }
    
    
        public int hashCode(Object o) {
            Pair p = (Pair)o;
            return p.a* 31 +p.b;
        }
    
    } 
    
    static class Pair1 implements Comparable<Pair1>
    {
       char a;
       int b;
        Pair1 (char a,int b)
        {
            this.a=a;
            this.b=b;
        }
     
        public int compareTo(Pair1 o) {
            
            if(this.a!=o.a)
            return Integer.compare(this.a,o.a);
            else
                return Integer.compare(this.b, o.b);
            //return 0;
        }
        public boolean equals(Object o) {
            if (o instanceof Pair1) {
                Pair1 p = (Pair1)o;
                return p.a == a && p.b == b;
            }
            return false;
        }
    
    
        public int hashCode(Object o) {
            Pair1 p = (Pair1)o;
            return (int)p.a* 31 +(int)p.b;
        }
    
    } 
   
    //public void solve(int testNumber, InputReader in, OutputWriter out) 
    
    // in case u want to print And take input inside and static method
    static void extendedEuclid( long A,  long B) {
        if(B==0)
        {d_ec=A;
          x_ec =1;
          y_ec=0;
      
        }
        else{
            extendedEuclid(B, A%B);
             long temp =x_ec;
            x_ec = y_ec;
            y_ec =temp -(A/B)*y_ec;
        }
          
      }
      static long modInverse( long A,  long M) //A and M are coprime i.e. Ax+My=1. In the extended Euclidean algorithm, x is the modular multiplicative inverse of A under modulo M.
      {
          extendedEuclid(A,M);
          return (x_ec%M+M)%M;    //x may be negative
      }
       /*
      static boolean checkprime(int N) {
          int count = 0;
          for( int i = 1;i * i <=N;++i ) {
               if( N % i == 0) {
                   if( i * i == N )
                           count++;
                   else       // i < sqrt(N) and (N / i) > sqrt(N)
                           count += 2;
                }
          }
          if(count == 2)
               return true;
          else
            return false;
      }
      static void factorize (long a,HashMap<Long,Long> map)
        {
          long i=2;
          for( i=2;i*i<=a;i++)
          {
            if(a%i==0){
                long f=0;  
            while((a>0)&&(a%i==0))
            { 
                a= a/i;
                f++;
            }
            map.put(i, f);
          
            }
          }
          if(a>1l)
            map.put(a, 1l);
    
        }*/
    
    /*static class DSU
    {
    int parent[];
    int rank[];
    int state[];
    DSU(int n)
    {parent=new int[n];
    rank=new int[n];
    state=new int[n+1];
        
    }
    void makeset(int n)
    {
    for(int i=0;i<n;i++)
    {
    parent[i]=i;
    rank[i]=1;
    state[i]=0;// for jamboard question
    }
    }
    void decP(int x)// for jamboard question
    {
    if(state[x]>0)
    state[x]--;
    }
    void incP(int x)// for jamboard question
    {
    state[x]++;
    }
    boolean getP(int x)// for jamboard question
    {
    return (state[x]!=0);
    }
    int find(int x)
    {
    if(x==parent[x])
    return x;
    parent[x]=find(parent[x]);
    return parent[x];
    }
    void union(int x,int y)
    {
    int xRoot=find(x);
    int yRoot=find(y);
    if(xRoot==yRoot)
    return;
    if(rank[xRoot]>rank[yRoot])
    {
    parent[yRoot]=xRoot;
    state[xRoot]+=state[yRoot];// for jamboard question
    }
    else if(rank[xRoot]<rank[yRoot])
    {
    parent[xRoot]=yRoot;
    state[yRoot]+=state[xRoot];// for jamboard question
    }
    else
    {
    parent[xRoot]=yRoot;
    rank[yRoot]++;
    state[yRoot]+=state[xRoot];// for jamboard question
    }
    }
    }
    */    

}/*
class DSU
{
int parent[];
int rank[];
int diff[];
DSU(int sd){
parent=new int[sd];
rank=new int[sd];
diff=new int[sd];
}
void makeset(int n)
{

for(int i=0;i<n;i++)
{
parent[i]=i;
rank[i]=1;
diff[i]=0;
}
}

int find (int x) {
    if (x == parent [x]) return x;
    int t = parent [x];
    parent [x] = find (parent [x]);
    diff [x] ^= diff [t];
    return parent [x];
}
boolean union(int x,int y,int w)
{
int xRoot=find(x); 
int yRoot=find(y);
if(xRoot==yRoot)
{ if(w != (diff[x]^diff[y]))
         return false;
}

else if(rank[xRoot]>rank[yRoot])
{
parent[yRoot]=xRoot;
diff[yRoot]= diff[x]^diff[y]^w;
}
else if(rank[xRoot]<rank[yRoot])
{
parent[xRoot]=yRoot;
diff[xRoot]= diff[x]^diff[y]^w;

}
else
{
parent[xRoot]=yRoot;
rank[yRoot]++;
diff[xRoot]= diff[x]^diff[y]^w;
}
return true;
}
}*/
class Gnode{
    int value;
    List<Gnode> neighbours;
    Gnode(int x)
   {value=x;
    neighbours =new ArrayList<>();
   }
   
   }
 class Node{
       int value;
       Node left;
       Node right;
       Node(int qw){
           this.value = qw;
           this.left = null;
           this.right = null;
       }
   }
   
   class SegTree{
       long[] seg;
       int[] map;
       long[] arr;
       SegTree(int n,long[] a){
           seg=new long[4*n];
           arr=a;
           map=new int[n+1];
       }
       void build(int low,int high, int pos) {
           if(low==high) {
               map[low]=pos;
               seg[pos]=arr[low];
           }
           else {
               int middle=(low+high)/2;
               build(low,middle,2*pos+1);
               build(middle+1,high,2*pos+2);
               seg[pos]=Math.max(seg[2*pos+1], seg[2*pos+2]);
           }
       }
       void update(int low,int high, int pos,int elpos, long value) {
           if(low==high) {
               seg[pos]=value;
           }
           else {
               int middle=(low+high)/2;
               if(elpos<=middle) {
                   update(low,middle,2*pos+1,elpos,value);
               }
               else update(middle+1,high,2*pos+2,elpos,value);
               seg[pos]=Math.max(seg[2*pos+1], seg[2*pos+2]);
           }
       }
   }

class MinHeap {
   int size;
   int maxsize;
   int heap[];
   MinHeap(int maxsize,int size)           //size = capacity
   {this.size=size;
    this.maxsize= maxsize;
    heap = new int[maxsize];

   }
   boolean isEmpty()
   {return size==0;
}
   int peek()
   {if(isEmpty())
     return -99999;
     return heap[0];

   }
   int remove()
   {if(isEmpty())
    return -99999;
    int minItem = heap[1];
    heap[1]= heap[size];
    size --;
    heapifyDown(1);
    return minItem;
   }
    void print()
    {
      System.out.println(Arrays.toString(heap)); 
    }
   boolean add( int item)
   {  if(size>= maxsize)
          return false;
          heap[size+1]= item;
          size++;
          heapifyUp(size);
          return true;

   }
    void heapifyDown( int i)
    { int left = 2*i;
        int right = 2*i +1;
        int smallest =i;
        if(left<= size  && heap[left]<heap[smallest])
          smallest =left;
          if(right<= size  && heap[right]<heap[smallest])
          smallest =right;
          if(smallest!=i)
          {  int temp =heap[i];
             heap[i]= heap[smallest];
             heap[smallest]=temp;
             heapifyDown(smallest);

          }

    }
    void heapifyUp( int i)
    {
        int parent = i/2;
        if( parent>0 && heap[parent]>heap[i])
        { int temp =heap[parent];
            heap[parent]= heap[i];
            heap[i]=temp;
            heapifyUp(parent);

        }
    }}
    class MaxHeap {
        int size;
        int maxsize;
        int heap[];
        MaxHeap(int maxsize,int size)           //size = capacity
        {this.size=size;
         this.maxsize= maxsize;
         heap = new int[maxsize];
     
        }
        void buildHeap(int arr[])
        {size = arr.length+1;
         for(int i=0;i<arr.length;i++)
        heap[i+1]= arr[i];
        for( int i=size/2;i>=1;i--)
        {heapifyDown(i);
            
        }

         
        }
        boolean isEmpty()
        {return size==0;
     }
        int peek()
        {if(isEmpty())
          return -99999;
          return heap[0];
     
        }
        int remove()
        {if(isEmpty())
         return -99999;
         int minItem = heap[1];
         heap[1]= heap[size];
         size --;
         heapifyDown(1);
         return minItem;
        }
         void print()
         {
           System.out.println(Arrays.toString(heap)); 
         }
        boolean add( int item)
        {  if(size>= maxsize)
               return false;
               heap[size+1]= item;
               size++;
               heapifyUp(size);
               return true;
     
        }
         void heapifyDown( int i)
         { int left = 2*i;
             int right = 2*i +1;
             int largest =i;
             if(left<= size  && heap[left]>heap[largest])
               largest =left;
               if(right<= size  && heap[right]>heap[largest])
               largest =right;
               if(largest!=i)
               {  int temp =heap[i];
                  heap[i]= heap[largest];
                  heap[largest]=temp;
                  heapifyDown(largest);
     
               }
     
         }
         void heapifyUp( int i)
         {
             int parent = i/2;
             if( parent>0 && heap[parent]<heap[i])
             { int temp =heap[parent];
                 heap[parent]= heap[i];
                 heap[i]=temp;
                 heapifyUp(parent);
     
             }
         }







}
 class InputReader
{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;
 
    public InputReader(InputStream stream)
    {
        this.stream = stream;
    }
 
    public int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read(buf);
            } catch (IOException e)
            {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
 
    public int readInt ()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public String readString ()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do
        {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
    public String readLine() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndOfLine(c));
        return res.toString();
    }
    
 
    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }
    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
    public boolean isSpaceChar(int c)
    {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
 
    public String next()
    {
        return readString();
    }
 
    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
    public boolean isEndOfLine(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }
}
class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0) {
                writer.print(' ');
            }
            writer.print(objects[i]);
        }
    }

    public void println(Object... objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

}