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 sys import stdin
from collections import deque
mod = 10**9 + 7
import sys
sys.setrecursionlimit(10**5)
from queue import PriorityQueue
# def rl():
#     return [int(w) for w in stdin.readline().split()]
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt,factorial,gcd,log2,inf,ceil
# map(int,input().split())
# # l = list(map(int,input().split()))
# from itertools import permutations
import heapq
# input = lambda: sys.stdin.readline().rstrip()
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop


# n,k = map(int,input().split())
#
# l = list(map(int,input().split()))


def solve(n):

    for i in range(2,int(sqrt(n)) + 1):
        if n%i == 0:
            return True



    return False




primes = []

for i in range(2,10**5 + 1):
    if not solve(i):
        primes.append(i)

n = int(input())
ans = 0
while n!=0:

    if n%2 == 0:
        ans+=n//2
        break
    flag = 0
    for i in primes:
        if n%i == 0:
            n-=i
            ans+=1
            flag = 1
            break
    if not flag:
     if not solve(n):

        ans+=1
        break

print(ans)





