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.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class round54b {
    private static List<Long> primes=new ArrayList<Long>(Arrays.asList(new Long[]{2l, 3l, 5l, 7l, 11l, 13l, 17l, 19l}));

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s=input.nextLine();
        long n=Long.parseLong(s);

        long res=0;
        long del;
        
        while (n!=0) {
            del=minPD(n);

            n=n-del;
            // System.out.println(n);
            res++;

            if (del==2) {
                res=res+n/2;
                n=0;
            }
        }

        System.out.println(res);


    }

    private static long minPD(long n){
        long sqr=(long)(Math.sqrt((double)n)+1);
        long k=3;

        if (n%2==0) return n/2;

        for(k=3; k<=sqr; k=k+2) if (n%k==0) break;

        if (k>sqr) return n;
        return k;
        /*
        long prime=2;
        for(int i=0; prime<=n; i++) {
            if (i>=primes.size()) next1000000Primes();
            prime=primes.get(i);
            if (n%prime==0) return prime;
        }
        return -1;
        */
    }

    private static long next1000000Primes(){
        if (primes.size()==8) System.out.print("Adding... ");
        long i=2+primes.get(primes.size()-1);

        for (int k=0; k<100000; k++) {
            for (int j = 0; (j < primes.size()) && (primes.get(j) * primes.get(j) < i); j++)
                if (i % primes.get(j) == 0) {
                    i = i + 2;
                    j = -1;
                    // System.out.println("j minimized");
                }

            primes.add(i);
            i=i+2;
        }
        System.out.println(i + "... ");
        return i;
    }
}
