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.Comparator;
import java.util.Scanner;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author mankank
 */
public class DivisorSubtraction {
    private static boolean checkPrime (long number) {
        if (number == 1) {
            return false;
        }
        for (int i = 2; i <= (number/2); i++) {
            if (number % i == 0) {
                return false;
            } 
            if (i != 2) 
                i++;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long ans = 0;
        //for (int k = 0; k <= 100; k++) {
        long n = sc.nextLong();
        long[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199};
        while (true) {
            boolean cf = false;
            for (int i = 0; i < primes.length; i++) {
                if (n % primes[i] == 0) {
                    long modvalue = n % primes[i];
                    if (primes[i] == 2) {
                        ans += (n / primes[i]);
                        n -= ((n / primes[i]) * primes[i]);
                        
                    }
                    else if (primes[i] != 2) {
                        ans++;
                        n -= primes[i];
                    }
                    cf = true;
                    break;
                }
            }
            if (!cf) {
                ans = 1; break;
            }
            if (n <= 0) break;
        }
        System.out.println(ans);
        //}
    }
}
class M implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        long v1 = (long)o1;
        long v2 = (long)o2;
        return v1 > v2 ? +1:-1;
    }
    
}
