You are given an integer number n. The following algorithm is applied to it:

  1. if n = 0, then end algorithm; 
  2. find the smallest prime divisor d of n; 
  3. subtract d from n and go to step 1. 



Determine the number of subtrations the algorithm will make.

Input

The only line contains a single integer n (2 ≤ n ≤ 10^{10}).

Output

Print a single integer — the number of subtractions the algorithm will make.

Examples

Input


5


Output


1


Input


4


Output


2

Note

In the first example 5 is the smallest prime divisor, thus it gets subtracted right away to make a 0.

In the second example 2 is the smallest prime divisor at both steps.

import java.util.*;
import java.io.*;
import java.math.*;
public class mmm
{
    static class InputReader {
        public BufferedReader br;
        public StringTokenizer token;
        public InputReader(InputStream stream)
        {
            br=new BufferedReader(new InputStreamReader(stream),32768);
            token=null;
        }

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

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

        public long nextLong()
        {
            return Long.parseLong(next());
        }
    }
    /*static class card{
    long up;
    int down;
    public card(long u,int d)
    {
    this.up=u;
    this.down=d;
    }
    }
    static class sort implements Comparator<card>
    {
    public int compare(card o1,card o2)
    {
    if(o1.up!=o2.up)
    return (int)(o1.up-o2.up);
    else
    return (int)(o1.down-o2.down);
    }
    }
    static void shuffle(long a[])
    {
    List<Long> l=new ArrayList<>();
    for(int i=0;i<a.length;i++)
    l.add(a[i]);
    Collections.shuffle(l);
    for(int i=0;i<a.length;i++)
    a[i]=l.get(i);
    }

    static long gcd(long a,long b)
    {
    if(b==0)
    return a;
    else
    return gcd(b,a%b);
    }
    static int ans1=Integer.MAX_VALUE,ans2=Integer.MAX_VALUE,ans3=Integer.MAX_VALUE,ans4=Integer.MAX_VALUE;
    static boolean v[]=new boolean[101];
    static void dfs(Integer so,Set<Integer> s[]){
    if(!v[so.intValue()])
    {
    v[so]=true;
    for(Integer h:s[so.intValue()])
    {
    if(!v[h.intValue()])
    dfs(h,s);
    }
    }
    }
    static class Print{
    public PrintWriter out;
    Print(OutputStream o)
    {
    out=new PrintWriter(o);
    }
    }
    static int CeilIndex(int A[], int l, int r, int key) 
    { 
    while (r - l > 1) { 
    int m = l + (r - l) / 2; 
    if (A[m] >= key) 
    r = m; 
    else
    l = m; 
    } 

    return r; 
    } 

    static int LongestIncreasingSubsequenceLength(int A[], int size) 
    { 
    // Add boundary case, when array size is one 
    int[] tailTable = new int[size]; 
    int len; // always points empty slot 
    tailTable[0] = A[0]; 
    len = 1; 
    for (int i = 1; i < size; i++) { 
    if (A[i] < tailTable[0]) 
    // new smallest value 
    tailTable[0] = A[i]; 

    else if (A[i] > tailTable[len - 1]) 
    // A[i] wants to extend largest subsequence 
    tailTable[len++] = A[i]; 

    else
    // A[i] wants to be current end candidate of an existing 
    // subsequence. It will replace ceil value in tailTable 
    tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]; 
    } 
    return len; 
    }*/
    /*static int binary(int n)
    {
    int s=1;
    while(n>0)
    {
    s=s<<1;
    n--;
    }
    return s-1;
    }
    static StringBuilder bin(int i,int n)
    {
    StringBuilder s=new StringBuilder();
    while(i>0)
    {
    s.append(i%2);
    i=i/2;
    }
    while(s.length()!=n)
    {
    s.append(0);
    }
    return s.reverse();
    }*/
    public static void main(String args[])
    {
        InputReader sc=new InputReader(System.in);
       long n=sc.nextInt();
       int a[]=new int[2000000];
       int sum=0;
       for(int i=2;i*i<=n;i++)
       {
           if(n%i==0)
           {
               while(n%i==0)
               {
                   a[i]++;
                   n=n/i;
               }
               sum+=a[i];
           }
       }
       if(n>0)
       {
           sum+=1;
       }
       System.out.println(sum);
    }
}
