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.IOException;
import java.io.OutputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        new Solver().solve(System.in , System.out);
    }

    private static class Solver {
        private final int SIZE = 1000001; // arbitrarily set :(
        private List<Integer> primes = new ArrayList<>();
        private void initPrimes() {
            boolean[] isPrime = new boolean[SIZE];
            for(int i = 2;i < SIZE;i++) {
                isPrime[i] = true;
            }

            for(int i = 2;i < SIZE;i++) {
                for(int j = 2;i * j < SIZE;j++) {
                    isPrime[i * j] = false;
                }
            }

            for(int i = 2;i < SIZE;i++) {
                if(isPrime[i]) {
                    primes.add(i);
                }
            }
        }

        private void solve(InputStream inStream , OutputStream outStream) {
            InputReader in = new InputReader(inStream);
            PrintWriter out = new PrintWriter(outStream);

            initPrimes();
            long n = in.nextLong(), res = 0;
            if(n % 2 == 0) {
                res = n / 2;
            } else {
                for(int prime : primes) {
                    if(n % prime == 0) {
                        n -= prime;
                        res++;
                        break;
                    }
                }
                res += n / 2;
            }

            out.println(res);
            out.close();
        }
    }

    public static class InputReader {
        private int pos;
        private String[] tokens;
        private BufferedReader reader;

        public InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while(tokens == null || pos == tokens.length) {
                try {
                    String line = reader.readLine();
                    if(line != null) {
                        tokens = line.split("\\s");
                        pos = 0;
                    }
                } catch(IOException e) {
                    e.printStackTrace();
                }
            }

            return tokens[pos++];
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];

            for(int i = 0;i < n;i++) {
                a[i] = nextInt();
            }

            return a;
        }
    }

}


