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.awt.*;
import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main implements Runnable {

    int maxn = (int)1e3+11;
    long inf = (long)1e18;
    long mod = (long)1e9+7;
    int n,m,k;

    void solve() throws Exception {
        long x = in.lLong();
        if (x%2==0) {
            out.println(x/2);
        } else {
            long ans = 0;
            long till = (long) Math.sqrt(x);
            for (long i=2; i<=till; i++) {
                while (x%i==0L) {
                    ans++;
                    x-=i;
                    break;
                }
            }

            if (ans==0L) {
                out.println(1);
                return;
            }

            ans += x/2L;
            out.println(ans);
        }


    }

    private HashMap<Integer, Integer> getFactorized(int x) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 2; i <= x; i++) {
            int cnt = 0;
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            if (cnt > 0) {
                map.put(i, cnt);
            }
        }
        return map;
    }

    String fileInName = "";

    static Throwable throwable;
    public static void main (String [] args) throws Throwable {
        Thread thread = new Thread(null, new Main(), "", (1 << 26));
        thread.start();
        thread.join();
        thread.run();
        if (throwable != null)
            throw throwable;
    }

    FastReader in;
    PrintWriter out;

    public void run() {

        try {
            if (!fileInName.isEmpty()) {
                in = new FastReader(new BufferedReader(new FileReader(fileInName+".in")));
                out = new PrintWriter(new BufferedWriter(new FileWriter(fileInName+".out")));
            } else {
                in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
                out = new PrintWriter(System.out);
            }

            solve();
        } catch(Exception e) {
            throwable = e;
        } finally {
            out.close();
        }

    }

    class FastReader {
        BufferedReader bf;
        StringTokenizer tk = null;

        public FastReader(BufferedReader bf) {
            this.bf = bf;
        }

        public Integer iInt() throws Exception {
            return Integer.parseInt(sString());
        }

        public Long lLong() throws Exception {
            return Long.parseLong(sString());
        }

        public Double dDouble() throws Exception {
            return Double.parseDouble(sString());
        }

        public String sString () throws Exception {
            if (tk==null || !tk.hasMoreTokens()) {
                tk = new StringTokenizer(bf.readLine());
            }
            if (!tk.hasMoreTokens()) return sString();
            else
                return tk.nextToken();
        }
    }
}