You can't possibly imagine how cold our friends are this winter in Nvodsk! Two of them play the following game to warm up: initially a piece of paper has an integer q. During a move a player should write any integer number that is a non-trivial divisor of the last written number. Then he should run this number of circles around the hotel. Let us remind you that a number's divisor is called non-trivial if it is different from one and from the divided number itself. 

The first person who can't make a move wins as he continues to lie in his warm bed under three blankets while the other one keeps running. Determine which player wins considering that both players play optimally. If the first player wins, print any winning first move.

Input

The first line contains the only integer q (1 ≤ q ≤ 1013).

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Output

In the first line print the number of the winning player (1 or 2). If the first player wins then the second line should contain another integer — his first move (if the first player can't even make the first move, print 0). If there are multiple solutions, print any of them.

Examples

Input

6


Output

2


Input

30


Output

1
6


Input

1


Output

1
0

Note

Number 6 has only two non-trivial divisors: 2 and 3. It is impossible to make a move after the numbers 2 and 3 are written, so both of them are winning, thus, number 6 is the losing number. A player can make a move and write number 6 after number 30; 6, as we know, is a losing number. Thus, this move will bring us the victory.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class A {

    public static int[] x = {0, 1, 0, -1, 1, -1, 1, -1};
    public static int[] y = {1, 0, -1, 0, 1, 1, -1, -1};

    public static void main(String[] args) {
        try {
            Scanner in = new Scanner();
            // PrintWriter out = new PrintWriter(new FileOutputStream(new File("vans.out")));
            PrintWriter out = new PrintWriter(System.out);
            boolean[] p = new boolean[10000001];
            ArrayList<Integer> list = new ArrayList();
            for (int i = 2; i < p.length; i++) {
                if (!p[i]) {
                    list.add(i);
                    for (int j = i * i; j < p.length; j += i) {
                        if (j <= i) {
                            break;
                        }
                        p[j] = true;
                    }
                }
            }
            long q = in.nextLong();
            long val = cal(q, list);
            if ( val != 2) {
                out.println(1);
                out.println(val);
            } else{
                out.println(val);
            }
            out.close();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    public static long cal(long val, ArrayList<Integer> list) {
        long start = list.get(0);
        int next = 1;
        long hold = val;
        ArrayList<Long> temp = new ArrayList();
        while (start * start <= val) {
            if (val % start == 0) {
                int count = 0;
                while (val % start == 0) {
                    count++;
                    val /= start;
                    temp.add(start);
                }
                if (temp.size() > 2) {
                    return temp.get(0) * temp.get(1);
                }

            }
            start = list.get(next++);
        }
        if (val != hold && val != 1) {
            temp.add(val);
        }
        if (temp.size() > 2) {
            return temp.get(0) * temp.get(1);
        }
        if (temp.size() > 0) {
            return 2;
        }

        return 0;

    }

    static class Triple implements Comparable<Triple> {

        int s, f, t;

        public Triple(int s, int f, int t) {
            this.s = s;
            this.f = f;
            this.t = t;
        }

        @Override
        public int compareTo(Triple o) {
            return t - o.t;
        }
    }

    static double dist(Point a, Point b) {
        long total = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
        return Math.sqrt(total);
    }

    static class Point {

        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;

        }
    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    static class FT {

        int[] data;

        FT(int n) {
            data = new int[n];
        }

        void update(int index, int val) {
            // System.out.println("UPDATE INDEX " + index);
            while (index < data.length) {
                data[index] += val;
                index += index & (-index);

                //    System.out.println("NEXT " +index);
            }
        }

        int get(int index) {
            //  System.out.println("GET INDEX " + index);
            int result = 0;
            while (index > 0) {
                result += data[index];
                index -= index & (-index);
                // System.out.println("BACK " + index);
            }
            return result;
        }
    }

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

    static int pow(int a, int b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        int val = pow(a, b / 2);
        if (b % 2 == 0) {

            return val * val;
        } else {
            return val * val * a;
        }
    }

//    static Point intersect(Point a, Point b, Point c) {
//        double D = cross(a, b);
//        if (D != 0) {
//            return new Point(cross(c, b) / D, cross(a, c) / D);
//        }
//        return null;
//    }
//
//    static Point convert(Point a, double angle) {
//        double x = a.x * cos(angle) - a.y * sin(angle);
//        double y = a.x * sin(angle) + a.y * cos(angle);
//        return new Point(x, y);
//    }
//    static Point minus(Point a, Point b) {
//        return new Point(a.x - b.x, a.y - b.y);
//    }
//
//    static Point add(Point a, Point b) {
//        return new Point(a.x + b.x, a.y + b.y);
//    }
//
//    static double cross(Point a, Point b) {
//        return a.x * b.y - a.y * b.x;
//
//
//    }
//
//    static class Point {
//
//        int x, y;
//
//        Point(int x, int y) {
//            this.x = x;
//            this.y = y;
//        }
//
//        @Override
//        public String toString() {
//            return "Point: " + x + " " + y;
//        }
//    }
    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            //System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //br = new BufferedReader(new FileReader(new File("vans.in")));
        }

        public String next() {


            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

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

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

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}
