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

public class Main {
	
	
	public static void main (String[] args) {
		BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
    	String str="";
        try {
        	//str = bi.readLine();
        	//int t = Integer.parseInt(str);
        	//for (int j=1;j<=t;j++)
        	{
        		str = bi.readLine();
        		Long n = Long.parseLong(str);
        		long steps = 0;
        		if (n%2==0)
        		{
        			System.out.println(n/2);
        			return;
        		}
        		long orig = n;
        		boolean [] prime = getPrime((int)Math.ceil(Math.sqrt(n))+1);
        		for (int i=2;i<=(int)Math.ceil(Math.sqrt(orig));i++)
        		{
        			if (prime[i] && n%i==0)
        			{
        				steps += 1;
        				n -= i;
        				i=2;
        			}
        			if (n%2==0)
        			{
        				System.out.println(steps + n/2);
        				return;
        			}
        		}
        		System.out.println(1);
        	}
        }
        catch (Exception e)
        {
        	
        }
	}
	
	public static boolean[] getPrime(int n)
	{
		boolean[] prime = new boolean[n];
		for (int i=2;i<n;i++)
		{
			prime[i] = true;
		}
		for (int i=2;i<n;i++)
		{
			if (prime[i]==true)
			{
				for (int j=i+1;j<n;j++)
				{
					if (j%i==0)
					{
						prime[j] = false;
					}
				}
			}
		}
		return prime;
	}
}
