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 org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

import java.io.*;
import java.math.*;
import java.util.*;



public class C {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        long n=sc.nextLong();
    //    HashSet set=sieveOfEratosthenes(n);
        BigInteger b=new BigInteger(""+n);
        if(b.isProbablePrime(80))
            System.out.println(1);
        else {
            int count=0;
            while (true){
                if(n%2==0){
                    count+=n/2;
                    break;
                }
                n=n-div(n);
                count++;
                
                if(n<=0)
                    break;
            }
            System.out.println(count);



        }







    }
    public static long div(long n)
    {
        long flag=0;
        for(int i=2;i<=n;i++){
            if(n%i==0){
                flag=i;
                break;
            }
        }
        return flag;
    }

  static  HashSet sieveOfEratosthenes(long n)
    {
        HashSet set=new HashSet();
        boolean prime[] = new boolean[(int)n+1];
        for(int i=0;i<n;i++)
            prime[i] = true;

        for(int p = 2; p*p <=n; p++)
        {
            // If prime[p] is not changed, then it is a prime
            if(prime[p] == true)
            {
                // Update all multiples of p
                for(int i = p*2; i <= n; i += p)
                    prime[i] = false;
            }
        }

        // Print all prime numbers
        for(int i = 2; i <= n; i++)
        {
            if(prime[i] == true)
                set.add(i);
        }
        return set;
    }

    static long gcd(long a , long b)
    {
        if(b == 0)
            return a;
        return gcd(b , a % b);
    }

}
class Scanner {
    public BufferedReader reader;
    public StringTokenizer st;

    public Scanner(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        st = null;
    }

    public String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = reader.readLine();
                if (line == null) return null;
                st = new StringTokenizer(line);
            } catch (Exception e) {
                throw (new RuntimeException());
            }
        }
        return st.nextToken();
    }

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

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

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

class OutputWriter {
    BufferedWriter writer;

    public OutputWriter(OutputStream stream) {
        writer = new BufferedWriter(new OutputStreamWriter(stream));
    }

    public void print(int i) throws IOException {
        writer.write(i);
    }

    public void print(String s) throws IOException {
        writer.write(s);
    }

    public void print(char[] c) throws IOException {
        writer.write(c);
    }

    public void close() throws IOException {
        writer.close();
    }

}