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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.*;
import java.io.*;
import java.math.*;
public class Main{

static class Pair
	{ 
		int x; 
		int y; 
		// Constructor 
		public Pair(int x, int y) 
		{	 
			this.x = x; 
			this.y = y; 
		}	 
	} 
	static class Compare
	{ 
		static void compare(Pair arr[], int n) 
		{ 
			// Comparator to sort the pair according to second element 
			Arrays.sort(arr, new Comparator<Pair>() { 
				@Override public int compare(Pair p1, Pair p2) 
				{ 
					return p2.y - p1.y; 
				} 
			}); 
		} 
	}
    public static long pow(long a, long b)
    {
        long result=1;
        while(b>0)
        {
            if (b % 2 != 0)
            {
                result=(result*a);
                b--;
            } 
            a=(a*a);
            b /= 2;
        }   
                return result;
    }
    public static BigInteger fact(long num)
    {
                BigInteger fact=new BigInteger("1");
                int i=0;
                for(i=1; i<=num; i++)
                {
                    BigInteger bg=BigInteger.valueOf(i);
                    fact=fact.multiply(bg);
                }
                return fact;
            }
            public static long gcd(long a, long b)
            {
                if (a == 0)
                    return b;
                return gcd(b%a, a);
            }
            
            public static long lcm(int a,int b)
            {
                return a * (b / gcd(a, b));
            }
            public static long sum(int h)
            {
                return (h*(h+1)/2);
            }
		/*	public static void dfs(int parent,boolean[] visited)
			{
				ArrayList<Integer> arr=new ArrayList<Integer>();
				arr=graph.get(parent);
				visited[parent]=true;
				storing1[parent]=count++;
				for(int i=0;i<arr.size();i++)
				{
					int num=arr.get(i);
					if(visited[num]==false)
					{
						dfs(num,visited);
					}
				}
				storing2[parent]=count;
			}
			static int count=0;
			static int[] storing1;
			static int[] storing2;
			static ArrayList<ArrayList<Integer>> graph;
		*/	public static void main(String args[])throws IOException
            {
                InputReader in=new InputReader(System.in);
        		OutputWriter out=new OutputWriter(System.out);
        	//	long a=pow(26,1000000005);
        	//    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        	    ArrayList<Integer> ar=new ArrayList<>();
				ArrayList<Integer> ar1=new ArrayList<>();
				TreeSet<Integer> ts=new TreeSet<>();
				TreeSet<Integer> ts1=new TreeSet<>();
				HashMap<Integer,Integer> hash=new HashMap<Integer,Integer>();
				TreeMap<String, Integer> tree=new TreeMap<String ,Integer>();
				long n=l();
				boolean[] prime=new boolean[1000001];
				for(int i=2;i*i<=1000000;i++)
				{
					if(prime[i]==false)
					{
						for(int j=2*i;j<=1000000;j+=i)
						{
							prime[j]=true;
						}
					}
				}
				if(n%2==0)
				{
					long ans=n/2;
					pln(ans+"");
				}
				else
				{
					int num=-1;
					for(int i=2;i<=Math.sqrt(n);i++)
					{
						if(n%i==0 && prime[i]==false)
						{
							num=i;
							break;
						}
					}
					if(num!=-1)
					{
						n=n-num;
						long ans=n/2+1;
						pln(ans+"");
					}
					else
					{
						pln("1");
					}
				}
			}
			
			
			
			/**/
			static InputReader in=new InputReader(System.in);
                static OutputWriter out=new OutputWriter(System.out);
                public static long l()
                {
                    String s=in.String();
                    return Long.parseLong(s);
                }
                public static void pln(String value)
                {
                    System.out.println(value);
                }
                public static int i()
                {
                    return in.Int();
                }
                public static String s()
                {
                    return in.String();
                }
	}
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
        class InputReader {
        	 
        	private InputStream stream;
        	private byte[] buf = new byte[1024];
        	private int curChar;
        	private int numChars;
        	private SpaceCharFilter filter;
         
        	public InputReader(InputStream stream) {
        		this.stream = stream;
        	}
         
        	public int read() {
        		if (numChars== -1)
        			throw new InputMismatchException();
        		if (curChar >= numChars) {
        			curChar = 0;
        			try {
        				numChars = stream.read(buf);
        			} catch (IOException e) {
        				throw new InputMismatchException();
        			}
        			if (numChars <= 0)
        				return -1;
        		}
        		return buf[curChar++];
        	}
         
        	public int Int() {
        		int c = read();
        		while (isSpaceChar(c))
        			c = read();
        		int sgn = 1;
        		if (c == '-') {
        			sgn = -1;
        			c = read();
        		}
        		int res = 0;
        		do {
        			if (c < '0' || c > '9')
        				throw new InputMismatchException();
        			res *= 10;
        			res += c - '0';
        			c = read();
        		} while (!isSpaceChar(c));
        		return res * sgn;
        	}
         
        	public String String() {
        		int c = read();
        		while (isSpaceChar(c))
        			c = read();
        		StringBuilder res = new StringBuilder();
        		do {
        			res.appendCodePoint(c);
        			c = read();
        		} while (!isSpaceChar(c));
        		return res.toString();
        	}
         
        	public boolean isSpaceChar(int c) {
        		if (filter != null)
        			return filter.isSpaceChar(c);
        		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        	}
         
        	public String next() {
        		return String();
        	}
         
        	public interface SpaceCharFilter {
        		public boolean isSpaceChar(int ch);
        	}
        }
         
        class OutputWriter {
        	private final PrintWriter writer;
         
        	public OutputWriter(OutputStream outputStream) {
        		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        	}
         
        	public OutputWriter(Writer writer) {
        		this.writer = new PrintWriter(writer);
        	}
         
        	public void print(Object...objects) {
        		for (int i = 0; i < objects.length; i++) {
        			if (i != 0)
        				writer.print(' ');
        			writer.print(objects[i]);
        		}
        	}
         
        	public void printLine(Object...objects) {
        		print(objects);
        		writer.println();
        	}
         
        	public void close() {
        		writer.close();
        	}
         
        	public void flush() {
        		writer.flush();
        	}
         
        	}
         
            class IOUtils {
         
        	public static int[] readIntArray(InputReader in, int size) {
        		int[] array = new int[size];
        		for (int i = 0; i < size; i++)
        			array[i] = in.Int();
        		return array;
        	}
         
        	} 