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.io.*;
import java.math.BigInteger;
import java.util.regex.*;

public class Codeforces{
	
	static class MyScanner{
		BufferedReader br;
		StringTokenizer st;
		
		MyScanner(FileReader fileReader){
			br = new BufferedReader(fileReader);
		}
		
		MyScanner(){
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		String nn(){
			while(st == null || !st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				}catch(IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		String nextLine(){
			String s = "";
			try{
				s = br.readLine();
			}catch(IOException e){
				e.printStackTrace();
			}
			return s;
		}
		
		int ni(){
			return Integer.parseInt(nn());
		}
		
		long nl(){
			return Long.parseLong(nn());
		}
		
		double nd(){
			return Double.parseDouble(nn());
		}
	}
	
	private static PrintWriter out;
	
	public static void main(String[] args) throws FileNotFoundException{
		
		// Input from file
		// File inputFile = new File("JavaFile.txt");
		// File outputFile = new File("JavaOutputFile.txt");
		// FileReader fileReader = new FileReader(inputFile);
		// Here it ends
			
		MyScanner sc = new MyScanner();
		// MyScanner sc = new MyScanner(fileReader);
		
		out = new PrintWriter(new BufferedOutputStream(System.out)); // Output to console
		// out = new PrintWriter(new PrintStream(outputFile)); // Output to file
		
		long n = sc.nl();
		long first = getDivisor(n);
		out.println(n / first);
		
		out.close();
	}
	
	private static long getDivisor(long n){
		long i = 1;
		TreeSet<Long> set = new TreeSet<>();
		while(i * i <= n){
			if(n % i == 0){
				if(isPrime(i)) return i;
				if(isPrime(n / i)) set.add(n / i);
			}
			i++;
		}
		if(set.size() > 0) return set.first();
		return 0;
	}
	
	private static boolean isPrime(long n){
		if(n == 1) return false;
		long i = 2;
		while(i * i <= n){
			if(n % i == 0) return false;
			i++;
		}
		return true;
	}
}