JATC's math teacher always gives the class some interesting math problems so that they don't get bored. Today the problem is as follows. Given an integer n, you can perform the following operations zero or more times:

  * mul x: multiplies n by x (where x is an arbitrary positive integer). 
  * sqrt: replaces n with √{n} (to apply this operation, √{n} must be an integer). 



You can perform these operations as many times as you like. What is the minimum value of n, that can be achieved and what is the minimum number of operations, to achieve that minimum value?

Apparently, no one in the class knows the answer to this problem, maybe you can help them?

Input

The only line of the input contains a single integer n (1 ≤ n ≤ 10^6) — the initial number.

Output

Print two integers: the minimum integer n that can be achieved using the described operations and the minimum number of operations required.

Examples

Input

20


Output

10 2

Input

5184


Output

6 4

Note

In the first example, you can apply the operation mul 5 to get 100 and then sqrt to get 10.

In the second example, you can first apply sqrt to get 72, then mul 18 to get 1296 and finally two more sqrt and you get 6.

Note, that even if the initial value of n is less or equal 10^6, it can still become greater than 10^6 after applying one or more operations.
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.*;
import java.io.*;
import java.math.*;
public class Main{

static class Pair
	{ 
		int x; 
		int y; 
		// Constructor 
		public Pair(int x, int y) 
		{	 
			this.x = x; 
			this.y = y; 
		}	 
	} 
	static class Compare
	{ 
		static void compare(Pair arr[], int n) 
		{ 
			// Comparator to sort the pair according to second element 
			Arrays.sort(arr, new Comparator<Pair>() { 
				@Override public int compare(Pair p1, Pair p2) 
				{ 
					return p2.y - p1.y; 
				} 
			}); 
		} 
	}
    public static long pow(long a, long b)
    {
        long result=1;
        while(b>0)
        {
            if (b % 2 != 0)
            {
                result=(result*a);
                b--;
            } 
            a=(a*a);
            b /= 2;
        }   
                return result;
    }
    public static BigInteger fact(long num)
    {
                BigInteger fact=new BigInteger("1");
                int i=0;
                for(i=1; i<=num; i++)
                {
                    BigInteger bg=BigInteger.valueOf(i);
                    fact=fact.multiply(bg);
                }
                return fact;
            }
            public static long gcd(long a, long b)
            {
                if (a == 0)
                    return b;
                return gcd(b%a, a);
            }
            
            public static long lcm(int a,int b)
            {
                return a * (b / gcd(a, b));
            }
            public static long sum(int h)
            {
                return (h*(h+1)/2);
            }
		/*	public static void dfs(int parent,boolean[] visited)
			{
				ArrayList<Integer> arr=new ArrayList<Integer>();
				arr=graph.get(parent);
				visited[parent]=true;
				storing1[parent]=count++;
				for(int i=0;i<arr.size();i++)
				{
					int num=arr.get(i);
					if(visited[num]==false)
					{
						dfs(num,visited);
					}
				}
				storing2[parent]=count;
			}
			static int count=0;
			static int[] storing1;
			static int[] storing2;
			static ArrayList<ArrayList<Integer>> graph;
		*/	public static void main(String args[])throws IOException
            {
                InputReader in=new InputReader(System.in);
        		OutputWriter out=new OutputWriter(System.out);
        	//	long a=pow(26,1000000005);
        	//    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        	    ArrayList<Integer> ar=new ArrayList<>();
				ArrayList<Integer> ar1=new ArrayList<>();
				TreeSet<Integer> ts=new TreeSet<>();
				TreeSet<Integer> ts1=new TreeSet<>();
				HashMap<Integer,Integer> hash=new HashMap<Integer,Integer>();
				TreeMap<String, Integer> tree=new TreeMap<String ,Integer>();
				int n=i();
				boolean[] prime=new boolean[n+1];
				for(int i=2;i<=Math.sqrt(n);i++)
				{
					if(prime[i]==false)
					{
						for(int j=2*i;j<=n;j+=i)
						{
							prime[j]=true;
						}
					}
				}
				if(n==1)
				{
					pln("1 0");
				}
				else
				{
					if(prime[n]==false)
					{
						pln(n+" 0");
					}
					else
					{
						int num=n;
					int[] count=new int[n+2];
					long ans=0;
					while(n%2==0) 
					{ 
						count[2]++;
						n /= 2; 
					} 
					for (int i = 3; i <= Math.sqrt(n); i+= 2) 
					{	 
						while (n%i == 0) 
						{ 
							count[i]++;
							n /= i; 
						}	 
					}
					if(n>2)
						count[n]++;
					long num1=1;
					for(int i=0;i<=num;i++)
					{
						ans+=(long)(Math.sqrt(count[i]));
						if(count[i]>0)
						{
							num1=num1*i;
						}
					}
					pln(num1+" "+ans);}
				}
			}
			
			
			
			/**/
			static InputReader in=new InputReader(System.in);
                static OutputWriter out=new OutputWriter(System.out);
                public static long l()
                {
                    String s=in.String();
                    return Long.parseLong(s);
                }
                public static void pln(String value)
                {
                    System.out.println(value);
                }
                public static int i()
                {
                    return in.Int();
                }
                public static String s()
                {
                    return in.String();
                }
	}
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
        class InputReader {
        	 
        	private InputStream stream;
        	private byte[] buf = new byte[1024];
        	private int curChar;
        	private int numChars;
        	private SpaceCharFilter filter;
         
        	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 int Int() {
        		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 String String() {
        		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 String();
        	}
         
        	public interface SpaceCharFilter {
        		public boolean isSpaceChar(int ch);
        	}
        }
         
        class OutputWriter {
        	private final PrintWriter writer;
         
        	public OutputWriter(OutputStream outputStream) {
        		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        	}
         
        	public OutputWriter(Writer writer) {
        		this.writer = new PrintWriter(writer);
        	}
         
        	public void print(Object...objects) {
        		for (int i = 0; i < objects.length; i++) {
        			if (i != 0)
        				writer.print(' ');
        			writer.print(objects[i]);
        		}
        	}
         
        	public void printLine(Object...objects) {
        		print(objects);
        		writer.println();
        	}
         
        	public void close() {
        		writer.close();
        	}
         
        	public void flush() {
        		writer.flush();
        	}
         
        	}
         
            class IOUtils {
         
        	public static int[] readIntArray(InputReader in, int size) {
        		int[] array = new int[size];
        		for (int i = 0; i < size; i++)
        			array[i] = in.Int();
        		return array;
        	}
         
        	} 