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 sys,math,io,os,time,itertools,collections
mod=10**9+7
sys.setrecursionlimit(10000)
i=sys.stdin.readline
p=sys.stdout.write
#use sys.stdout.write() (remember to convert to str b4 and concatenate "\n")
global start,end

def primefac(n):
    l=[]
    while n%2==0:
        l.append(2)
        n=n//2
    p=3
    while p*p<=n:
        while n%p==0:
            l.append(p)
            n=n//p
        p+=2
    if n>2:
        l.append(n)
    return l[0]

def main():
    n=int(i())
    count=0
    while n:
        if primefac(n)==2:
            count+=n//2
            break
        n=n-primefac(n)
        count+=1
    p(str(count)+"\n")

t=1
#t=int(i())
start=time.perf_counter()
for _ in range(t):
    main()
end=time.perf_counter()
#print(end-start)