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:
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;

public class Main implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        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 String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            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 long nextLong() {
            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 double nextDouble() {
            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, nextInt());
                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, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            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 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 static void main(String args[]) throws Exception {
        new Thread(null, new Main(), "Main", 1 << 27).start();
    }

    static class Pair {
        int f;
        int s;
        PrintWriter w;

        // int t;

        Pair(int f, int s) {
            // Pair(int f,int s, PrintWriter w){
            this.f = f;
            this.s = s;
            // this.w = w;
            // this.t = t;

        }

        public static Comparator<Pair> wc = new Comparator<Pair>() {
            public int compare(Pair e1, Pair e2) {

                // 1 for swap
                if (Math.abs(e1.f) - Math.abs(e2.f) != 0) {
                    // e1.w.println("**"+e1.f+" "+e2.f);
                    return (Math.abs(e1.f) - Math.abs(e2.f));
                } else {
                    // e1.w.println("##"+e1.f+" "+e2.f);
                    return (Math.abs(e1.s) - Math.abs(e2.s));
                }

            }
        };
    }

    public static long gcd(long a, long b) {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    //// recursive BFS
    public static int bfsr(int s, ArrayList<Integer>[] a, boolean[] b, int[] pre) {
        b[s] = true;
        int p = 1;
        int n = pre.length - 1;
        int t = a[s].size();
        int max = 1;
        for (int i = 0; i < t; i++) {
            int x = a[s].get(i);
            if (!b[x]) {
                // dist[x] = dist[s] + 1;
                int xz = (bfsr(x, a, b, pre));
                p += xz;
                max = Math.max(xz, max);
            }
        }
        // max = Math.max(max,(n-p));
        pre[s] = max;
        return p;
    }

    //// iterative BFS
    public static int bfs(int s, ArrayList<Integer>[] a, int dist, boolean[] b, PrintWriter w) {
        b[s] = true;
        int siz = 0;
        dist--;
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        while (q.size() != 0 && dist > 0) {
            int i = q.poll();
            Iterator<Integer> it = a[i].listIterator();
            int z = 0;
            while (it.hasNext() && dist > 0) {
                z = it.next();
                if (!b[z]) {
                    b[z] = true;
                    dist--;
                    // dist[z] = dist[i] + 1;
                    siz++;
                    q.add(z);
                }
            }

        }
        return siz;
    }

    public static int lower(int key, Integer[] a) {
        int l = 0;
        int r = a.length - 1;
        int res = 0;

        while (l <= r) {
            int mid = (l + r) / 2;

            if (a[mid] <= key) {
                l = mid + 1;
                res = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return res;
    }

    public static long power(long x, long y, long m) {
        if (y == 0)
            return 1;

        long p = power(x, y / 2, m) % m;
        p = (p * p) % m;

        if (y % 2 == 0)
            return p;
        else
            return (x * p) % m;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////////////

    public void run() {
        // code here
        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);

        long defaultValue = 0;
        long mod = Long.valueOf("1000000007");

        int tc = sc.nextInt();
        while (tc-- > 0) {
            long m = sc.nextLong();
            long n = m;
            HashMap<Long, Long> hm = new HashMap<Long, Long>();
            ArrayList<Long> a = new ArrayList<Long>();
            if (n % 2 == 0)
                a.add((long) 2);
            while (n % 2 == 0) {
                hm.put((long) 2, hm.getOrDefault((long) 2, defaultValue) + 1);
                n /= 2;
            }

            // n must be odd at this point. So we can
            // skip one element (Note i = i +2)
            for (int i = 3; i <= Math.sqrt(n); i += 2) {
                // While i divides n, print i and divide n
                if (n % i == 0)
                    a.add((long) i);
                while (n % i == 0) {
                    hm.put((long) i, hm.getOrDefault((long) i, defaultValue) + 1);
                    n /= i;
                }
            }
            // if(n>2){

            // }
            long ans = 0;
            long aa = m;
            // w.println("* " + a.size());
            for (int i = 0; i < a.size(); i++) {
                long x = a.get(i);
                // w.print("# " + x);
                long z = hm.get(x);
                // w.println(" " + z);
                if (z > 1) {
                    if (z - 1 > ans) {
                        ans = z - 1;
                        aa = x;
                    }
                }
            }
            w.println(ans + 1);
            // if(ans==0){
            // w.println(n);
            // continue;
            // }
            int z = (int) (long) hm.getOrDefault(aa, defaultValue);
            for (int i = 1; i < z; i++) {
                w.print(aa + " ");
                m = m / aa;
            }
            w.println(m);

        }
        w.flush();
        w.close();

    }
}