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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.math.BigInteger;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
        public static void main(String[] args) {
                InputStream inputStream = System.in;
                OutputStream outputStream = System.out;
                InputReader in = new InputReader(inputStream);
                PrintWriter out = new PrintWriter(outputStream);
                TaskB solver = new TaskB();
                solver.solve(1, in, out);
                out.close();
        }

        static class TaskB {
                public void solve(int testNumber, InputReader in, PrintWriter out) {
                        long n = in.l();

                        if (BigInteger.valueOf(n).isProbablePrime(1)) {
                                out.println(1);
                                return;
                        }

                        int[] primeList = SieveUtil.linearSieveStoresFirstPrime(1000000 + 6)[0];

                        out.println(countSteps(primeList, n));
                }

                private long countSteps(int[] primeList, long n) {
                        if (n % 2 == 0) {
                                return n / 2;
                        }

                        long start = firstEvenAfterSubtractingPrime(primeList, n);
                        if (BigInteger.valueOf(start).isProbablePrime(1)) {
                                return 2;
                        }
                        return (start / 2) + 1;
                }

                private long firstEvenAfterSubtractingPrime(int[] primeList, long n) {
                        for (int prime : primeList) {
                                if (n % prime == 0) {
                                        return n - prime;
                                }
                        }
                        return 1;
                }

        }

        static class InputReader {
                InputStream is;
                private byte[] inbuf = new byte[1024];
                public int lenbuf = 0;
                public int ptrbuf = 0;

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

                private int readByte() {
                        if (lenbuf == -1) throw new InputMismatchException();
                        if (ptrbuf >= lenbuf) {
                                ptrbuf = 0;
                                try {
                                        lenbuf = is.read(inbuf);
                                } catch (IOException e) {
                                        throw new InputMismatchException();
                                }
                                if (lenbuf <= 0) return -1;
                        }
                        return inbuf[ptrbuf++];
                }

                public long l() {
                        long num = 0;
                        int b;
                        boolean minus = false;
                        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
                        if (b == '-') {
                                minus = true;
                                b = readByte();
                        }

                        while (true) {
                                if (b >= '0' && b <= '9') {
                                        num = num * 10 + (b - '0');
                                } else {
                                        return minus ? -num : num;
                                }
                                b = readByte();
                        }
                }

        }

        static class SieveUtil {
                public static int[][] linearSieveStoresFirstPrime(int N) {
                        int[] store = new int[N];
                        int[] prime = new int[N];
                        int k = 0;
                        Arrays.fill(store, 0);
                        store[1] = 1;
                        for (int i = 2; i < N; i++) {
                                if (store[i] == 0) {
                                        prime[k++] = i;
                                        store[i] = i;
                                }
                                for (int j = 0; j < k && i * prime[j] < N && prime[j] <= store[i]; j++) {
                                        store[i * prime[j]] = prime[j];
                                        if (i % prime[j] == 0) break;
                                }
                        }
                        prime = Arrays.copyOf(prime, k);
                        return new int[][]{prime, store};
                }

        }
}

