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

Solution:
//package cf671;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class E {
    static boolean CONSTRUCTIVE = true;
    static long MOD = (long) 1e9 + 7;
    static long BIG = (long) 2e9;
    static long[] factorials;
    static SortedSet<Integer> primes;

    public static void solve(Reader in, PrintWriter out) {
        long n = in.nextLong();
        SortedMap<Integer, Integer> fact = primeFactorization(n);
        if (fact.size() == 2 && fact.values().stream().allMatch(x->x==1)) {
            for (int i : fact.keySet()) {
                out.print(i + " ");
            }
            out.println(n);
            out.println(1);
        } else {
            List<Integer> div = divisors(fact);
            for (int i : div) {
                out.print(i + " ");
            }
            out.println();
            out.println(0);
        }
    }

    static List<Integer> divisors(SortedMap<Integer, Integer> fact) {
        if (fact.isEmpty()) return new ArrayList<>();
        int prime = fact.firstKey();
        int power = fact.remove(prime);
        List<Integer> prev = divisors(fact);
        List<Integer> powers = new ArrayList<>();
        List<Integer> mixed = new ArrayList<>();
        for (int pow = 1; pow <= power; pow++) {
            powers.add((int) pow(prime, pow));
        }
        int max = Integer.MIN_VALUE;
        for (int i : prev) {
            for (int pow = 1; pow <= power; pow++) {
                mixed.add(i * (int) pow(prime, pow));
                max = Math.max(max, i * (int) pow(prime, pow));
            }
        }
        List<Integer> res = new ArrayList<>();
        if (max > Integer.MIN_VALUE && mixed.size() > 1) {
            res.add(max);
            mixed.remove(Integer.valueOf(max));
        }
        Collections.reverse(powers);
        res.addAll(powers);
        Collections.reverse(mixed);
        res.addAll(mixed);
        res.addAll(prev);

//        System.out.println("powers " + powers);
//        System.out.println("mixed " + mixed);
//        System.out.println("prev " + prev);
        return res;
    }

    public static void main(String[] args) throws IOException {
        computePrimes(32_000);
        Reader in = null;
        PrintWriter out = null;
        for (String arg : args) {
            if (arg.startsWith("input")) {
                in = new Reader(arg);
            } else if (arg.startsWith("output")) {
                out = new PrintWriter(new FileWriter(arg));
            }
        }
        if (in == null) in = new Reader();
        if (out == null) out = new PrintWriter(new OutputStreamWriter(System.out));

        int tests = in.nextInt();
        for (int t = 0; t < tests; t++) {
            solve(in, out);
        }

        out.flush();
    }

    static class Tester {
        public static void main(String[] args) throws IOException {
            E.Validator validator = new E.Validator();

            File currentDir = new File(".");
            long before;
            long after;
            for (File inputFile : Arrays.stream(currentDir.listFiles())
                    .sorted(Comparator.comparing(File::getName))
                    .collect(Collectors.toList())) {
                if (!inputFile.getName().startsWith("input")
                        || inputFile.getName().contains("sight")
                        || inputFile.getName().contains("big")) continue;
                System.out.println("Test file: " + inputFile.getName());

                before = System.nanoTime();
                String outputFileName = "output" + inputFile.getName().substring(5);
                E.main(new String[]{inputFile.getName(), outputFileName});
                after = System.nanoTime();

                File outputFile = new File(outputFileName);
                if (!outputFile.exists()) {
                    throw new IllegalStateException("Missing output file " + outputFile);
                }

                // TODO if verifier is implemented, remove this
                if (CONSTRUCTIVE) {
                    System.out.println("INPUT:");
                    printFile(inputFile);
                    System.out.printf("\nOUTPUT: (%d milliseconds)\n", (after - before) / 1000000L);
                    printFile(outputFile);
                    continue;
                }

                if (validator.validate(inputFile, outputFile)) {
                    System.out.printf("OK (%d milliseconds)\n", (after - before) / 1000000L);
                } else {
                    System.out.println("FAILED");
                    System.out.println("\nInput: ");
                    printFile(inputFile);
                    System.out.println("\nIncorrect Output: ");
                    printFile(outputFile);
                    return;
                }
            }
            System.out.println("\n-----------------\n");

            File sightTestInput = new File("input-sight");
            if (sightTestInput.exists()) {
                System.out.println("Running sight test... Input:");
                printFile(sightTestInput);
                before = System.nanoTime();
                System.out.println("\nOutput: ");
                E.main(new String[]{"input-sight"});
                after = System.nanoTime();
                System.out.printf("(%d milliseconds)\n", (after - before) / 1000000L);
                System.out.println("\n-----------------\n");
            }

            File bigTestInput = new File("input-big");
            if (bigTestInput.exists()) {
                System.out.println("Running big test...");
                before = System.nanoTime();
                E.main(new String[] {"input-big"});
                after = System.nanoTime();
                System.out.printf("(%d milliseconds)\n", (after - before) / 1000000L);
            }
        }

        static void printFile(File file) throws FileNotFoundException {
            BufferedReader reader = new BufferedReader(new FileReader(file));
            reader.lines().forEach(System.out::println);
        }
    }

    static class Validator {
        boolean validate(File inputFile, File outputFile) throws IOException {
            File expectedOutputFile = new File("expected-output" + inputFile.getName().substring(5));
            if (CONSTRUCTIVE || !expectedOutputFile.exists()) {
                return validateManual(inputFile, outputFile);
            }
            return areSame(outputFile, expectedOutputFile);
        }

        private boolean validateManual(File inputFile, File outputFile) throws IOException {
            if (CONSTRUCTIVE) {
                // Validate output against input
                E.Reader inputReader = new E.Reader(inputFile.getName());
                E.Reader outputReader = new E.Reader(outputFile.getName());

                // TODO implement manual validation

                throw new IllegalStateException("Missing expected output file");
            } else {
                File naiveOutput = new File("naive-" + outputFile.getName());
                E.Naive.main(new String[]{inputFile.getName(), naiveOutput.getName()});

                return areSame(outputFile, naiveOutput);
            }
        }

        private boolean areSame(File file1, File file2) throws IOException {
            BufferedReader reader1 = new BufferedReader(new FileReader(file1));
            BufferedReader reader2 = new BufferedReader(new FileReader(file2));

            String line1;
            while ((line1 = reader1.readLine()) != null) {
                String line2 = reader2.readLine();
                if (line2 == null) line2 = ""; // ok if one has an extra newline
                if (!line1.trim().equals(line2.trim())) {
                    return false;
                }
            }
            String line2;
            while ((line2 = reader2.readLine()) != null) {
                if (!line2.trim().isEmpty()) {
                    return false;
                }
            }
            return true;
        }

    }

    static class Naive {
        public static void solveNaive(E.Reader in, PrintWriter out) {
            throw new IllegalStateException("missing expected output file");
        }

        public static void main(String[] args) throws IOException {
            E.Reader in = null;
            PrintWriter out = null;
            for (String arg : args) {
                if (arg.startsWith("input")) {
                    in = new E.Reader(arg);
                } else if (arg.startsWith("naive-output")) {
                    out = new PrintWriter(new FileWriter(arg));
                }
            }
            if (in == null) in = new E.Reader();
            if (out == null) out = new PrintWriter(new OutputStreamWriter(System.out));

            int tests = in.nextInt();
            for (int t = 0; t < tests; t++) {
                solveNaive(in, out);
            }

            out.flush();
            out.close();
        }
    }

    static void computePrimes(int upto) {
        SortedSet<Integer> localPrimes = new TreeSet<>();
        boolean[] sieve = new boolean[upto]; // true = composite
        for (int i = 2; i <= Math.sqrt(upto); i++) {
            for (int k = i * 2; k < sieve.length; k += i) {
                sieve[k] = true;
            }
        }
        for (int i = 2; i < sieve.length; i++) {
            if (!sieve[i]) {
                localPrimes.add(i);
            }
        }
        primes = localPrimes;
    }

    static SortedMap<Integer, Integer> primeFactorization(long x) {
        if (x == 1) {
            return new TreeMap<>();
        }
        for (int prime : primes) {
            if (x % prime == 0) {
                int power = 1;
                long primePower = prime;
                while (x % (primePower * prime) == 0) {
                    power++;
                    primePower *= prime;
                }
                SortedMap<Integer, Integer> res = primeFactorization(x / primePower);
                res.put(prime, power);
                return res;
            }
        }
        // it's a prime too big for the sieve
        TreeMap<Integer, Integer> ret = new TreeMap<>();
        ret.put((int) x, 1);
        return ret;
    }

    static void computeFactorials(int upto) {
        factorials = new long[upto+1];
        factorials[0] = 1;
        for (int i = 1; i <= upto; i++) {
            factorials[i] = factorials[i - 1] * i;
        }
    }

    static void computeFactorialsMod(int upto) {
        factorials = new long[upto + 1];
        factorials[0] = 1L;
        for (int i = 1; i <= upto; i++) {
            factorials[i] = (factorials[i - 1] * i) % MOD;
        }
    }

    static long binom(long n, long k) {
        if (k == 0) return 1;
        if (k == 1) return n;

        long result = 1;
        for (int i = 0; i < k; i++) {
            result *= n - i;
            result /= i + 1;
        }
        return result;
    }

    static long pow(long base, long exp) {
        if (exp == 0) return 1;
        if (exp == 1) return base;
        long x = pow(base, exp / 2);
        long ans = (exp % 2 == 0) ? x * x : base * x * x;
        return ans;
    }

    static boolean isPowerOfTwo(int x) {
        return x > 0 & (x & (x - 1)) == 0;
    }

    static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    static long pair(int x, int y) {
        return x * BIG + y;
    }

    static int x(long pair) {
        return (int) (pair / BIG);
    }

    static int y(long pair) {
        return (int) (pair % BIG);
    }


    static class Reader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Reader() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }

        public Reader(String fileName) throws FileNotFoundException {
            reader = new BufferedReader(new FileReader(fileName));
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int[] nextInts(int n) {
            int[] out = new int[n];
            for (int i = 0; i < n; i++) {
                out[i] = nextInt();
            }
            return out;
        }

        public long[] nextLongs(int n) {
            long[] out = new long[n];
            for (int i = 0; i < n; i++) {
                out[i] = nextLong();
            }
            return out;
        }
    }
}