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.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class B1076 {
	public static void main(String[] args) throws FileNotFoundException {
		Scanner scan = new Scanner(System.in);
		long n = scan.nextLong();
		System.out.println(isPrime(n));
		if(isPrime(n)) {
			System.out.println(1);
			System.exit(0);
			
		}else {
			if(n % 2 == 0) {
				System.out.println(n /2);
				System.exit(0);
			}else {
				long spd = smallestPrimeDiv(n);
				n -= spd;
				System.out.println(n/2 + 1);
			}
		}

		
		
		
		

		
	}


	static long smallestPrimeDiv(long n){
		for(int i =2 ; i < n ; i ++) {
			if(n % i == 0) {
				if(isPrime(i)) {
					return i;
				}
			}
		}
		return n;
	}
	/*static boolean isPrime(long n) {
		for(int i= 2; i <n-1; i ++) {
			if(n % i == 0) {
				return false;
			}
		}
		return true;
	}
	*/
	static boolean isPrime(long n) {
	    if(n < 2) return false;
	    if(n == 2 || n == 3) return true;
	    if(n%2 == 0 || n%3 == 0) return false;
	    long sqrtN = (long)Math.sqrt(n)+1;
	    for(long i = 6L; i <= sqrtN; i += 6) {
	        if(n%(i-1) == 0 || n%(i+1) == 0) return false;
	    }
	    return true;
	}
}
