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

public class Main{
    
    ArrayList< ii > factor(long x){
        ArrayList< ii > ret = new ArrayList< ii >();
        for(long i=2; i*i<=x; ++i) if(x%i == 0){
            int contains = 0;
            while(x%i == 0){
                ++contains;
                x /= i;
            }
            ret.add(new ii(i, contains));
        }
        if(x!=1)
            ret.add(new ii(x, 1));
        return ret;
    }

    public void go(){
        long ret = Long.parseLong(sc.nextToken());

        ArrayList< ii > a = factor(ret);

        int sumP = 0;
        for(ii i : a) sumP += i.y;

        if(sumP < 2){
            System.out.printf("1\n0\n");
            return;
        }

        if(sumP == 2){
            System.out.printf("2\n");
            return;
        }

        ret = a.get(0).x;
        if(a.get(0).y>1)
            ret *= a.get(0).x;
        else
            ret *= a.get(1).x;
        System.out.printf("1\n%d\n", ret);

    }

    // syntax
    // ArrayList<Integer>[] myMat = (ArrayList<Integer>[]) new ArrayList[nB];

    // Pairs
    public class ii implements Comparable< ii >{
        long x, y;
        public ii(){}
        public ii(long xx, long yy){ x=xx; y=yy; }
        public int compareTo(ii p){ return 1; } //x!=p.x ? x-p.x : y-p.y; }
        // public int hashCode(){ return 31*x+y; }
        public boolean equals(Object o){
            if(!(o instanceof ii)) return false;
            ii p = (ii) o;
            return x==p.x && y==p.y;
        }
        public String toString(){ return "("+x+", "+y+")"; }
    }
/*
    public class pair< X extends Comparable< X >,Y extends Comparable< Y > > implements Comparable< pair< X,Y > >{
        X x;
        Y y;
        public pair(){}
        public pair(X xx, Y yy){ x=xx; y=yy; }
        public int compareTo(pair< X,Y > p){ return x.compareTo(p.x)!=0 ? x.compareTo(p.x) : y.compareTo(p.y); }
        public int hashCode(){ return 31*x.hashCode()+y.hashCode(); }
        public boolean equals(Object o){
            if((o.getClass() != this.getClass())) return false;
            pair< X,Y > p = (pair< X,Y >) o;
            return x.equals(p.x) && y.equals(p.y);
        }
        public String toString(){ return "("+x+", "+y+")"; }
    }
*/
    // my stuff
    public static final int INF = 1000*1000*1000+7;
    public static final double EPS = 1e-9;
    public static final double PI = 2*acos(0.0);
    public void rev(Object[] a){ for(int i=0; i<a.length/2; ++i){ Object t=a[i]; a[i]=a[a.length-1-i]; a[a.length-1-i]=t; } }
    public void rev(int[] a){ for(int i=0; i<a.length/2; ++i){ int t=a[i]; a[i]=a[a.length-1-i]; a[a.length-1-i]=t; } }
    public int bit_count(long x){ return x==0 ? 0 : 1+bit_count(x&(x-1)); }
    public int low_bit(int x){ return x&-x; } // 0011 0100 returns 0000 0100
    public int sign(int x){ return x<0 ? -1 : x>0 ? 1 : 0; }
    public int sign(double x){ return x<-EPS ? -1 : x>EPS ? 1 : 0; }
    int[] unpack(ArrayList< Integer > a){
        int[] ret = new int[a.size()];
        for(int i=0; i<a.size(); ++i) ret[i] = a.get(i);
        return ret;
    }

    // generic main stuff
    static myScanner sc;
    static PrintWriter pw;
    static long startTime;
    public static void main(String[] args) throws Exception{
        // sc = new Scanner(System.in);
        sc = (new Main()).new myScanner(new BufferedReader(new InputStreamReader(System.in)));
        pw = new PrintWriter(System.out);
        startTime = System.nanoTime();
        (new Main()).go();
        // errprintln("nanoTime="+(System.nanoTime()-startTime)/1000000/1000.0);
        pw.flush();
        System.exit(0);
    }

    // capable of reading   2.86M 6dp doubles per second
    //                      2.16M 12dp doubles per second
    //                      2.75M int per second
    public class myScanner{
        private BufferedReader f;
        private StringTokenizer st;
        public myScanner(BufferedReader ff){ f=ff; st=new StringTokenizer(""); }
        public int nextInt(){ return Integer.parseInt(nextToken()); }
        public double nextDouble(){ return Double.parseDouble(nextToken()); }
        public String nextLine(){
            st=new StringTokenizer("");
            String ret="";
            try{ ret=f.readLine(); }catch(Exception e){}
            return ret;
        }
        public String nextToken(){
            while(!st.hasMoreTokens()) try{ st=new StringTokenizer(f.readLine()); } catch(Exception e){}
            return st.nextToken();
        }
    }


}
