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.util.*;

public class Solution{
	InputStream is;
	static PrintWriter out;
	String INPUT = "";
	static long mod = (long)1e9+7L;
	
	int[] pf = sieveOfErosthenes(1000000);
	public void solve(){
		long n = nl();
		long d = lpf(n);
		out.println(n/d);
	}
	
	long lpf(long n){
		TreeSet<Long> fac = new TreeSet<Long>();
		long i = 2;
		for(; i*i <= n; i = i+1L){
			if(n% i == 0)
				return i;	
		}

		return n;


		/*long i;
		for(i = 2L; i*i <= n; i = i+1L){
			if(n%i == 0){
				fac.add(i);
				fac.add(n/i);
			}
		}

		fac.add(n);
		for(Long l : fac){
			if(l > 150000)return l;
			if(primes.contains(l))return l;
		}

		return fac.last();
	*/
	}

static TreeSet<Long> primes=new TreeSet<Long>();
static int[] sieveOfErosthenes(int n){
	int arr[]=new int[n+1];
	
	for(int i=2;i<=n;i++)arr[i]=i;
	
	for(int i=2;i*i<=n;i++){
		if(arr[i]==i){
			for(int j=i+i;j<=n;j+=i)if(arr[j]==j)arr[j]=i;
		}
	}
	for(int i=2;i<=n;i++)if(arr[i]==i)primes.add((long)i);
	return arr;
}
	void run(){
		is = new DataInputStream(System.in);
		out = new PrintWriter(System.out);
		int t=1;while(t-->0)solve();
		out.flush();
	}
	public static void main(String[] args)throws Exception{new Solution().run();}
	long mod(long v, long m){if(v<0){long q=(Math.abs(v)+m-1L)/m;v=v+q*m;}return v%m;}
    long mod(long v){if(v<0){long q=(Math.abs(v)+mod-1L)/mod;v=v+q*mod;}return v%mod;}
	//Fast I/O code is copied from uwi code.
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	private int readByte(){
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	private String ns(){
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	private char[] ns(int n){
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	private char[][] nm(int n, int m){
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	private int[] na(int n){
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	private int ni(){
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	private long nl(){
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	static  int i(long x){return (int)Math.round(x);}
	static class Pair implements Comparable<Pair>{
		long fs,sc;
		Pair(long a,long b){
			fs=a;sc=b;
		}
		public int compareTo(Pair p){
			if(this.fs>p.fs)return 1;
			else if(this.fs<p.fs)return -1;
			else{
				return i(this.sc-p.sc);
			}
			//return i(this.sc-p.sc);
		}
		public String toString(){
			return "("+fs+","+sc+")";
		}	
	}
	
}