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.
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
import sys
import math
MAX = sys.maxsize
MAXN = 10**6+10
def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def mhd(a,b,x,y):
    return abs(a-x)+abs(b-y)

def numIN():
    return(map(int,sys.stdin.readline().strip().split()))

def charIN():
    return(sys.stdin.readline().strip().split())

def primeFactors(n):
	cnt = 0
	while n % 2 == 0: 
		cnt+=1 
		n = n // 2

	for i in range(3,int(math.sqrt(n))+1,2): 

# while i divides n , print i ad divide n 
		while n % i== 0: 
			cnt+=1 
			n = n // i 

	if n > 2: 
		cnt+=1
	return cnt


print(primeFactors(int(input())))

