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.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class B {
	IO io = new IO();
	boolean[] isPrime = new boolean[100100];
	List<Integer> primes = new ArrayList<>();
	
	void preprocess() {
		for(int i=2; i<isPrime.length; i++) isPrime[i] = true;
		for(int i=2; i<isPrime.length; i++) {
			if(isPrime[i]) {
				primes.add(i);
				for(int j=i+i; j<isPrime.length; j+=i) {
					isPrime[j] = false;
				}
			}
		}
	}
	
	void begin() {
		preprocess();
		long N = io.nextLong();
		long div = N;
		
		for(int tdiv : primes) {
			if(N % tdiv == 0) {
				div = tdiv;
				break;
			}
		}
		long ans = N / div;
		io.out("%d\n", ans);
		
		io.done();
	}
	
	public static void main(String[] args) {
		(new B()).begin();
	}
	
	static class IO {
		BufferedReader reader;
		StringTokenizer tokenizer;
		BufferedWriter writer;
		boolean isAutoFlush;
		
		public IO() {
			this(false, null, null);
		}
		
		public IO(boolean isAutoFlush, String fileFrom, String fileTo) {
			if(fileFrom == null) {
				reader = new BufferedReader(new InputStreamReader(System.in));
			} else {
				try {
					reader = new BufferedReader(new FileReader(new File(fileFrom)));
				} catch(IOException e) {
					throw new RuntimeException(e);
				}
			}
			
			if(fileTo == null) {
				writer = new BufferedWriter(new OutputStreamWriter(System.out));
			} else {
				try {
					writer = new BufferedWriter(new FileWriter(new File(fileTo)));
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			
			tokenizer = new StringTokenizer("");
		}
		
		private String next() {
			while (!tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) { //EOF
					e.printStackTrace();
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public String nextString() {
			return next();
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		
		public void out(String format, Object... args) {
			try {
				String string = String.format(format, args);
				writer.write(string);
				if(isAutoFlush) writer.flush();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		
		public void done() {
			try {
				writer.flush();
				reader.close();
				writer.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}

}
