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 Main
{  
    static BufferedReader br;
    static StringTokenizer st;
    
    public static void main(String[] args) throws IOException 
	{
		br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

            long n = nxtLong();
            int cnt = 0;
            boolean flg = false;
            for(int i=2; i<=(int) Math.ceil(Math.sqrt(n)); i++) 
            {
                if(n %i == 0) 
                {
                    flg = true;
                    cnt = i;
                    break;
                }
            }
            System.out.println(flg? 1 + (n-cnt) / 2: 1);
    }
    
    static int nxtInt(){
        return Integer.parseInt(st.nextToken());
    }
    
    static long nxtLong(){
        return Long.parseLong(st.nextToken());
    }
    
    static double nxtDoub(){
        return Double.parseDouble(st.nextToken());
    }
    
    static String nxt(){
        return st.nextToken();
    }
    
    static String nxtLn() throws IOException{
        return br.readLine();
    }
}