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.lang.*;
import java.io.*;
public class Main{
	static Scanner sc = new Scanner(System.in);
	

	static final int MAX = 1000005;
    static int[] is_prime = new int[MAX];		// prime numbers using seive
    
	static long getl() {
		return sc.nextLong();
	}
	
	static int geti() {
		return sc.nextInt();
	}
	
	static String gets() {
		return sc.next();
	}
	
	static int[] intArr(int n) {
		int[] arr = new int[n];
		for(int i=0;i<n;i++) arr[i] = geti();
		return arr;
	}
	
	static long[] longArr(int n) {
		long[] arr = new long[n];
		for(int i=0;i<n;i++) arr[i] = getl();
		return arr;
	}
   
	static void print(String s) {
		System.out.print(s);
	}
	
	static void plarr(long[] arr) {
		for(int i=0;i<arr.length;i++) print(arr[i] + " ");
	}
	
	static void piarr(int[] arr) {
		for(int i=0;i<arr.length;i++) print(arr[i] + " ");
	}
	
	
    public static void main(String args[]){
    	long n = getl();
    	long res = 0;
    	boolean prime = true;
    	long div = 1;
    	for(long i=2;i*i<=n;i++) {
    		if(n%i==0) {
    			prime = false;
    			div = i;
    			break;
    		}
    	}
    	if(prime) res= 1;
    	else {
    		res++;
    		n -= div;
    		res += n/2;
    	}
    	print(res+"\n");
    }
}

