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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class q5 {

	 public static int gcd(int a,int b) {
		 if(b==0) return a;
		 else return gcd(b,a%b);
	 }
	 
	 
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Reader.init(System.in);
		long n=Reader.nextLong();
		long ans=0;
		if(n%2==0) {
			ans=n/2;
		}
		else {
			long d=(long)Math.sqrt(n);
			long smallest=0;
			for(int i=2;i<=d;i++) {
				if(n%i==0) {
					smallest=i;
					break;
				}
			}
			if(smallest==0) smallest=n;
			ans++;
			n=n-smallest;
			if(n!=0) {
				ans+=n/2;
			}
		}
		System.out.println(ans);
		
			
		
				
			
	}
}

 
 
 class DisJoint {
		int[] parent;
		int[] rank;
		int[] size;
		DisJoint(int n){
			
			parent=new int[n+1];
			rank=new int[n+1];
			size=new int[n+1];
			for(int i=0;i<=n;i++) {
				parent[i]=i;
				size[i]=1;
			}
		}

		int find(int value) {
			int par=parent[value];
			if(par==value)
				return par;
			parent[value]=find(par);
			return parent[value];
		}
		
		void union(int data1,int data2) {
			int parent1=find(data1);
			int parent2=find(data2);
			if(parent1!=parent2) {
				if(rank[parent1]>=rank[parent2]) {
					parent[parent2]=parent1;
					if(rank[parent1]==rank[parent2])
						rank[parent1]++;
					size[parent1]+=size[parent2];
				}
				else {
					parent[parent1]=parent2;	
					size[parent2]+=size[parent1];
		}

		}
		}
}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
 
    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
 
    /** get next word */
    
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
 
    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}
