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.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;


public class C107 {

	/**
	 * @param args
	 */
	
	static final double inf = Double.MAX_VALUE / 11; 
	  int kvad(int a) {return a*a;} 
	  double kvad(double a) {return a*a;} 
	  int gcd(int a, int b) {int c;while (a!=0) {c = a;a = b%a;b = c;}return b;} 
	  private HashMap memo = new HashMap(); 
	  static final int antInd = 4; 
	
	private void run() throws IOException{
		// TODO Auto-generated method stub
		
		long q=nextLong();
		
		
		int count=count(q);
		if(count<2){
			System.out.println(1);
			System.out.println(0);
			return ;
		}
		if(count==2){
			System.out.println(2);
			return;
		}
		System.out.println(1);
		for (long i = 2; i*i <= q; i++) {
			if(q%i==0){
				if(count(i) == 2){
					System.out.println(i);
					return ;
				}
                if(count(q/i)==2) {
                	System.out.println(q/i);
                	return ;
                }
			}
			
		}
		System.out.println(0);
		
		
		
	}
	
	private int gcd2(int q) {
		// TODO Auto-generated method stub
		return 0;
	}
	private int count(long n){
		 int result = 0;
         for (long i = 2; i*i <=n ; i++) {
             while(n %i == 0){
                 n/=i;
                 result++;
             }
         }
         if(n != 1 ) result++;
         return result;
	}
	private boolean isprime(int q) {
		// TODO Auto-generated method stub
		if(q==1||q==2||q==3)return true;
		
		for(int i=2;i*i<=q;i+=2) {
	        if(q%i==0)
	            return false;
	    }
		return true;
	}
	private int nextInt() throws IOException {
		if (!input.hasMoreTokens())input=new StringTokenizer(in.readLine());
		return Integer.parseInt(input.nextToken());
	}
	private long nextLong() throws IOException {
		if (!input.hasMoreTokens())input=new StringTokenizer(in.readLine());
		return Long.parseLong(input.nextToken());
	}
	private double nextDouble() throws IOException {
		if (!input.hasMoreTokens())input=new StringTokenizer(in.readLine());
		return Double.parseDouble(input.nextToken());
	}
	private String nextString() throws IOException {
		if (!input.hasMoreTokens())input=new StringTokenizer(in.readLine());
		return input.nextToken();
	}
	private void write(String output){
		out.write(output);
		out.flush();
	}
	private void writeln(String output){
		out.write(output+"\n");
//		out.flush();
	}
	private void end() throws IOException{
		in.close();
		out.close();
		System.exit(0);
	}
	
	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer input;
	
	public C107 () throws IOException {
		//Input Output for Console to be used for trying the test samples of the problem 
//		in = new BufferedReader(new InputStreamReader(System.in));
//		out = new PrintWriter(System.out);
		//-------------------------------------------------------------------------
		//Input Output for File to be used for solving the small and large test files
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter("clocks.out");
		//-------------------------------------------------------------------------
		//Initialize Stringtokenizer input
		input = new StringTokenizer(in.readLine());
	}
	
	public static void main(String[] args) throws Exception {
		//-------------------------------------------------------------------------
		//initializing...
		C107  sol = new C107 ();
		//-------------------------------------------------------------------------
		sol.run();
		//-------------------------------------------------------------------------
		//closing up
		sol.end();
		//--------------------------------------------------------------------------
	}
	

}
