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

public class ProbB {
   BufferedReader in;
   StringTokenizer str;
   PrintWriter out;
   String SK;
   String next() throws IOException {
      while ((str == null) || (!str.hasMoreTokens())) {
      SK = in.readLine();
      if (SK == null)
      return null;
      str = new StringTokenizer(SK);
      }
      return str.nextToken();
   }
   String nexts()throws IOException {
      return in.readLine();
   }
   int nextInt() throws IOException {
      return Integer.parseInt(next());
   }
   double nextDouble() throws IOException {
      return Double.parseDouble(next());
   }
   long nextLong() throws IOException {
      return Long.parseLong(next());
   }
   char[] charArray() throws IOException{
      return next().toCharArray();
   }
   public static void main(String[] args) throws IOException {
      new ProbB().run();
   }
   void run() throws IOException {
      in = new BufferedReader(new InputStreamReader(System.in));
      out = new PrintWriter(System.out);
      //in = new BufferedReader(new FileReader("input.txt"));
      //out = new PrintWriter("output.txt");
      solve();
      out.close();
   }
   void solve() throws IOException {
     long s =nextLong();
     int rr= (int)Math.sqrt((double)s);
      
     boolean pr[] = new boolean[rr+10000]; 
        for(int i=0;i<rr+1000;i++) 
            pr[i] = true; 
          
        for(int p = 2; p <pr.length; p++) 
        { 
            if(pr[p] == true) 
            { 
                
                for(int i = p*2; i < pr.length; i += p) 
                    pr[i] = false; 
            } 
        } 
        
        for (int i = 2; i <pr.length; i++) {
           if(pr[i] && s%i==0){
               System.out.println(s/i);
               return;
           }
       }
        System.out.println(1);
        
   }
   
   
}