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.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.*;
import java.math.BigInteger;

public class Main {

    InputReader in;
    Printer out;

    long mod = 1000000007;
    long inf = 100000000000L;

    boolean notPrime[] = new boolean[100005];

    private void start() throws Exception {
        long n = in.nextLong();

        if (n % 2 == 0) {
            out.println(n / 2);
            return;
        }

        for (int i = 2; i * i <= 100000; i++) {
            if (notPrime[i]) {
                continue;
            }

            for (int j = 2; i * j <= 100000; j++) {
                notPrime[i * j] = true;
            }
        }

//        out.println(Arrays.toString(notPrime));
        long firstPrimeFactor = n;
        for (int i = 2; i <= 100000; i++) {
            if (notPrime[i]) {
                continue;
            }

            if (n % i == 0) {
                firstPrimeFactor = i;
                break;
            }
        }

//        out.println("firstPrimeFactor " + firstPrimeFactor);

        out.println((n - firstPrimeFactor) / 2 + 1);
    }

    public long GCD(long a, long b) { return b==0L ? a : GCD(b, a%b); }

    long power(long x, long n, long mod) {
        if (n <= 0) {
            return 1;
        }

        long y = power(x, n / 2, mod);

        if ((n % 2) == 0) {
            return (y * y) % mod;
        } else {
            return (((y * y) % mod) * x) % mod;
        }
    }

    long gcd(long a, long b) {
        return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
    }

    public static void main(String[] args) throws Exception {
        InputReader in;
        PrintStream out;

//        in = new InputReader(new FileInputStream(new File("in.txt")));
        in = new InputReader(System.in);
        out = System.out;

        Main main = new Main();

        main.in = in;
        main.out = new Printer(out, true);

        main.start();
        main.out.flush();
    }


}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

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

    public int read() {
        if (numChars == -1) {
            throw new InputMismatchException();
        }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buf[curChar++];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public double nextDouble() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E') {
                return res * Math.pow(10, nextInt());
            }
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null) {
            return filter.isSpaceChar(c);
        }
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public String next() {
        return nextString();
    }

    public interface SpaceCharFilter {

        public boolean isSpaceChar(int ch);
    }
}

class Printer {

    PrintStream out;
    StringBuilder buffer = new StringBuilder();
    boolean autoFlush;

    public Printer(PrintStream out) {
        this.out = out;
    }

    public Printer(PrintStream out, boolean autoFlush) {
        this.out = out;
        this.autoFlush = autoFlush;
    }

    public void println() {
        buffer.append("\n");

        if (autoFlush) {
            flush();
        }
    }

    public void println(int n) {
        println(Integer.toString(n));
    }

    public void println(long n) {
        println(Long.toString(n));
    }

    public void println(double n) {
        println(Double.toString(n));
    }

    public void println(float n) {
        println(Float.toString(n));
    }

    public void println(boolean n) {
        println(Boolean.toString(n));
    }

    public void println(char n) {
        println(Character.toString(n));
    }

    public void println(byte n) {
        println(Byte.toString(n));
    }

    public void println(short n) {
        println(Short.toString(n));
    }

    public void println(Object o) {
        println(o.toString());
    }

    public void println(Object[] o) {
        println(Arrays.deepToString(o));
    }

    public void println(String s) {
        buffer.append(s).append("\n");

        if (autoFlush) {
            flush();
        }
    }

    public void print(char s) {
        buffer.append(s);

        if (autoFlush) {
            flush();
        }
    }

    public void print(String s) {
        buffer.append(s);

        if (autoFlush) {
            flush();
        }
    }

    public void flush() {
        try {
            BufferedWriter log = new BufferedWriter(new OutputStreamWriter(out));
            log.write(buffer.toString());

            log.flush();
            buffer = new StringBuilder();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class DisjointUnionSets {

    int[] rank, parent;
    int n;

    // Constructor
    public DisjointUnionSets(int n) {
        rank = new int[n];
        parent = new int[n];
        this.n = n;
        makeSet();
    }

    // Creates n sets with single item in each
    void makeSet() {
        for (int i = 0; i < n; i++) {
            // Initially, all elements are in
            // their own set.
            parent[i] = i;
        }
    }

    // Returns representative of x's set
    int find(int x) {
        // Finds the representative of the set
        // that x is an element of
        if (parent[x] != x) {
            // if x is not the parent of itself
            // Then x is not the representative of
            // his set,
            parent[x] = find(parent[x]);

            // so we recursively call Find on its parent
            // and move i's node directly under the
            // representative of this set
        }

        return parent[x];
    }

    // Unites the set that includes x and the set
    // that includes x
    void union(int x, int y) {
        // Find representatives of two sets
        int xRoot = find(x), yRoot = find(y);

        // Elements are in the same set, no need
        // to unite anything.
        if (xRoot == yRoot) {
            return;
        }

        // If x's rank is less than y's rank
        if (rank[xRoot] < rank[yRoot]) // Then move x under y  so that depth
        // of tree remains less
        {
            parent[xRoot] = yRoot;
        } // Else if y's rank is less than x's rank
        else if (rank[yRoot] < rank[xRoot]) // Then move y under x so that depth of
        // tree remains less
        {
            parent[yRoot] = xRoot;
        } else // if ranks are the same
        {
            // Then move y under x (doesn't matter
            // which one goes where)
            parent[yRoot] = xRoot;

            // And increment the the result tree's
            // rank by 1
            rank[xRoot] = rank[xRoot] + 1;
        }
    }
}