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 com.sun.org.apache.xalan.internal.xsltc.compiler.util.Type;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class h{
   static boolean [] prime ;
    static void seve(long n){
        for (int i =2;i*1l*i<=n;i++){
            if (prime[i]){
                for (int p=i*2;p<prime.length;p+=i){
                    prime[p]=false;
                }
            }
        }
    }
    static int getp(long n){
        int p =-1;
        for (int i =2;i<prime.length;i++){
            if (prime[i]){
                if (n%i==0){
                    return i;
                }
            }
        }
        return p;
    }
    public static void main(String[]args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n =Long.parseLong(br.readLine());
        prime = new boolean[10000001];
        Arrays.fill(prime,true);
        seve(n);
        long p =getp(n);
        long ans=0;
        ans++;

        if (p==-1){
            System.out.println(ans);
            return;
        }

        else if (n%2==0){
            n-=2;
            ans+=n/2;
        }
        else {
            n-=p;
            ans+=n/2;
        }

        System.out.println(ans);
}
}

