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

public class B {
	private static InputReader in = new InputReader(System.in);
	private static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) {
		new B().solve();
	}

	private final void solve() {
		long n = in.nextLong();
		for(int i = 2; i * 1L * i <= n; ++i) {
			if(n % i == 0) {
				out.println(n / i);
				done();
			}
		}

		out.println(1);
		done();
	}

	private final void done() {
		out.flush();
		out.close();
		System.exit(0);
	}
}

class InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024 << 3];
	private int curChar;
	private int numChars;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int[] readIntArray(int tokens) {
		int[] ret = new int[tokens];
		for (int i = 0; i < tokens; i++) {
			ret[i] = nextInt();
		}
		return ret;
	}

	public int read() {
		if (this.numChars == -1) {
			throw new InputMismatchException();
		} else {
			if (this.curChar >= this.numChars) {
				this.curChar = 0;

				try {
					this.numChars = this.stream.read(this.buf);
				} catch (IOException ex) {
					throw new InputMismatchException();
				}

				if (this.numChars <= 0) {
					return -1;
				}
			}

			return this.buf[this.curChar++];
		}
	}

	public int nextInt() {
		int c;
		for (c = this.read(); isSpaceChar(c); c = this.read()) {
		}

		byte sgn = 1;
		if (c == 45) {
			sgn = -1;
			c = this.read();
		}

		int res = 0;

		while (c >= 48 && c <= 57) {
			res *= 10;
			res += c - 48;
			c = this.read();
			if (isSpaceChar(c)) {
				return res * sgn;
			}
		}

		throw new InputMismatchException();
	}

	public long nextLong() {
		int c;
		for (c = this.read(); isSpaceChar(c); c = this.read()) {
		}

		byte sgn = 1;
		if (c == 45) {
			sgn = -1;
			c = this.read();
		}

		long res = 0;

		while (c >= 48 && c <= 57) {
			res *= 10L;
			res += c - 48;
			c = this.read();
			if (isSpaceChar(c)) {
				return res * sgn;
			}
		}
		throw new InputMismatchException();
	}

	public double nextDouble() {
		double ret = 0, div = 1;
		int c = read();
		while (c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if (neg)
			c = read();

		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');

		if (c == '.') {
			while ((c = read()) >= '0' && c <= '9') {
				ret += (c - '0') / (div *= 10);
			}
		}

		if (neg)
			return -ret;
		return ret;
	}

	public String next() {
		int c;
		while (isSpaceChar(c = this.read())) {
		}

		StringBuilder result = new StringBuilder();
		result.appendCodePoint(c);

		while (!isSpaceChar(c = this.read())) {
			result.appendCodePoint(c);
		}

		return result.toString();
	}

	public String nextLine() {
		int c;
		StringBuilder result = new StringBuilder();
		boolean read = false;
		while ((c = this.read()) != '\n') {
			if (c == -1)
				return null;
			result.appendCodePoint(c);
			read = true;
		}
		if (!read)
			return null;
		return result.toString();
	}

	public static boolean isSpaceChar(int c) {
		return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
	}
}