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 jdk.swing.interop.SwingInterOpUtils;
import org.w3c.dom.ls.LSOutput;

import java.util.*;
import java.util.function.IntBinaryOperator;


public class Example {
    static long[][] dp;
    //  static    int[]  ar;
    static int mod = 1000000000 + 7;
    static long[] ans = new long[100000 + 1];
    static List<List<Integer>> adj;
    static int[] vis;
    static int[] dis;
    static int row;
    static boolean[] chosen;
    static List<Integer> permutation;
    static int k;
    static int count;
    static int[][] arr;

    public static void main(String[] args) {

Scanner sc= new Scanner(System.in);
long p=0;
long n = sc.nextLong();
if(IsPrime(n)){
    System.out.println(1);
}else{

    long c=0;
  for(long i=2;i*i<=n;i++){
      if(n%i==0){
          p=i;
          break;
      }
  }
   // System.out.println(p);
  if(p==2){
      System.out.println(n/p);
  }else{
      if((n-p)%2==0){
          System.out.println(1+(n-p)/2);
      }else {
          for(long i=2;i<=n;i++){
              if((n-i*p)==0){
                  System.out.println(i+(n-i*p)/2);
                  break;
              }
          }
      }



  }

}
     


    }

    private static boolean IsPrime(long n) {
        for(long i=2;i*i<=n;i++){
            if(n%i==0){
                return false;

            }
        }
        return true;
    }

    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    private static void dfs(int v) {
        vis[v] = 1;
        for (int i : adj.get(v)) {
            if (vis[i] == 0) {
                dfs(i);
            }
        }
    }

    static class Pair {
        int a, b;

        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }


}

