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.Scanner;
public class Main {
    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        long n = s.nextLong();
        if(isPrime(n)){
            System.out.print(1);
            return;
        }
        
        if(n%2 == 0){
            System.out.print(n/2);
            return;
        }
        long ans = 0;
        if(n % 3 == 0){
            n = n - 3;
            ans++;
        }
        else if(n % 5 == 0){
            n = n - 5;
            ans++;
        }
        else if(n % 7 == 0){
            n = n - 7;
            ans++;
        }
       if(ans == 1){ 
          System.out.println(ans + n/2);
          return;
       }
       for(int i = 11; i <= Math.sqrt(n); i = i + 2){
           if(n % i == 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0){
               n = n - i + 2;
               break;
           }
       }
       System.out.println(n/2);

    }  
     static boolean isPrime(long n) 
    { 
        // Corner case 
        if (n <= 1) 
            return false; 
  
        // Check from 2 to n-1 
        for (int i = 2; i <= Math.sqrt(n); i++) 
            if (n % i == 0) 
                return false; 
  
        return true; 
    } 
  
}