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.

def sieve(n):
    arr = [1]*(n+1)
    arr[0] = 0
    arr[1] = 0
    
    for x in range(2,int(n**0.5)+1):
        if arr[x] == 1:
            arr[x*x::x] = [0 for i in arr[x*x::x]]

    return [x for x in range(len(arr)) if arr[x] == 1]

def smallest_div(n, primes):
    for x in primes:
        if n % x == 0:            
            return x
        
    return n

def solve():
    n = int(input())
    
    primes = sieve(int(n**0.5)+1)
    res = 0

    while n > 0: 
        n -= smallest_div(n, primes)
        res += 1
        
        while n > 0 and n % 2 == 0:            
            res += n//2
            n = 0
        
    print (res)
    
solve()

