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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class f {
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		
		long n = Long.parseLong(in.readLine().trim());

		
		long[] primes = cribaEratostenes((int)Math.sqrt(n) + 10);
		
		
		long cont = 0;
		int index = 0;
		while(n % primes[index] != 0 && primes[index] * primes[index] < n)
			index++;

		if(index == 0)
			cont = n / 2;
		else {
			if(n % primes[index] == 0) {
				cont = (n - primes[index])/2 + 1;
			}
			else
				cont = 1;
		}

		out.println(cont);
		
		out.close();
	}
	
	private static long[] cribaEratostenes(int n) {
		boolean [] num = new boolean[n];
		for (int i = 3; i * i < n; i+= 2) {
			if(!num[i]){
				for (int j = 2; i*j < n; j++)
					num[i*j] = true;
			}
		}
		long[] primos = new long[n];
		primos[0] = 2;
		int j = 1;
		for (int i = 3; i < num.length; i+= 2)
			if (!num[i]) primos[j++] = i;
		return Arrays.copyOf(primos, j);
	}
}
