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

public class B {
	public static void main(String args[])throws IOException {
		IO io = new IO();
		StringBuilder out = new StringBuilder("");

		long n = io.nextLong();
		long spf, steps;
		
		spf = smallestPrimeFactor(n);
		if(n%2==0) steps = n/2;
		else {
		    n -= spf;
		    steps = n/2 + 1;
		}

		System.out.println(steps);
	}
	
	static long smallestPrimeFactor(long n) {
	    
	    if( (n&1) == 0) return 2;
	    long limit = (long)Math.sqrt(n);
	    
	    long f=3;
	    while(f<=limit) {
	        if(n%f==0 && isPrime(f)) 
	            return f;
	        f += 2;
	    }
	            
	    return n;
	}
	
	static boolean isPrime(long n) {
	    if(n==2) return true;
	    if(n%2==0 || n==1) return false;
	    long limit = (long)Math.sqrt(n);
	    for(long i=3;i<=limit;i+=2)
	        if(n%i==0) return false;
	    return true;
	}

	static final long P = (long)1e9 + 7;

	static long power(long x, long y) 
	{ 
			long res = 1;      
			x = x % P;  
			while (y > 0) 
			{ 
					if((y & 1)==1) 
							res = (res * x) % P; 
					y = y >> 1;  
					x = (x * x) % P;  
			} 
			return res; 
	} 

	static long modProduct(long... a) {
		long sum = 1;
		for(long x : a) 
			sum = ( (sum%P) * (x%P) )%P;
		
		return sum;
	}


	static long modAdd(long... a) {
		long sum = 0;
		for(long x : a) {
			sum = ( (sum%P) + (x%P) )%P;
		}
		
		return sum;
	}

	static int min(int a, int b) { return a<b ? a : b; }
	static long min(long a, long b) { return a<b ? a : b; }
	static double min(double a, double b) { return a<b ? a : b; }

	static int max(int a, int b) { return a>b ? a : b; }
	static long max(long a, long b) { return a>b ? a : b; }
	static double max(double a, double b) { return a>b ? a : b; }
}

class IO {
	private BufferedReader br;
	private StringTokenizer st;

	IO()throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
	}

	String next()throws IOException {
		if(st.hasMoreTokens())
			return st.nextToken();

		st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	int nextInt()throws IOException { return Integer.parseInt(next()); }
	double nextDouble()throws IOException { return Double.parseDouble(next()); }
	long nextLong()throws IOException { return Long.parseLong(next()); }

	int[] nextIntArray(int n)throws IOException { 
		int[] a = new int[n];
		for(int i=0;i<n;i++) a[i] = nextInt();
		return a;
	}

	long[] nextLongArray(int n)throws IOException {
		long[] a = new long[n];
		for(int i=0;i<n;i++) a[i] = nextLong();
		return a;
	}

	double[] nextDoubleArray(int n)throws IOException {
		double[] a = new double[n];
		for(int i=0;i<n;i++) a[i] = nextDouble();
		return a;
	}
}

