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 get_res(n):
    result = 0
    if is_zhi(n):
        result = 0
    while(n):
        if n == 2:
            result+=1
            break
        if is_zhi(n) or n<2:
            break
        if n>2:
            n-=2
            result+=1
    return result


def is_zhi(num):
    result = 0
    if num<=1:
        result = 0
    elif num==2:
        result = 1
    else:
        i=2
        while i<num:
            if num%i==0:
                result = 0
                break
            i=i+1
        else:
            result = 1
    return  result

n = int(input())
result = get_res(n)
print result
  	   	 	        	 	 	  	 			