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.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner write = new Scanner(System.in);
        long N = write.nextLong();
        ArrayList<Integer> prost = new ArrayList <>();
        boolean[] prosti = new boolean[1000000];

        long chys = N;
        long d = 2;
        while(d*d<=chys){
            if(chys % d==0){
                chys/=d;
                break;
            }
            d++;
        }
        if(chys==N){
            System.out.println(1);
            return;
        }
        for(int i =2;i<prosti.length;i++){
            prosti[i] = true;
        }
        for(int i = 2 ;i<prosti.length;i++){
            if(prosti[i]){
                for(long j =(long)i*i;j<prosti.length;j+=i){
                    prosti[(int)j] = false;
                }
            }
        }
        for(int i = 2;i<prosti.length;i++){
            if(prosti[i]){
                prost.add(i);
            }
        }
        long cnt = 0;
        while(N!=0) {
            for (int i = 0; i < prost.size(); i++) {
                if (N % prost.get(i) == 0) {
                    if(prost.get(i)==2){
                        cnt+=N/prost.get(i);
                        N = 0;
                        break;
                    }
                    else {
                        cnt++;
                        N -= prost.get(i);
                        break;
                    }
                }
            }
        }
        System.out.println(cnt);

    }
}
