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 os import path
import sys,time
# mod = int(1e9 + 7)
# import re
from math import ceil, floor,gcd,log,log2 ,factorial
from collections import defaultdict ,Counter , OrderedDict , deque
from itertools import combinations , groupby , zip_longest,permutations
# from string import ascii_lowercase ,ascii_uppercase
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
#----------------------------INPUT FUNCTIONS------------------------------------------#
I = lambda :int(sys.stdin.buffer.readline())
tup= lambda : map(int , sys.stdin.buffer.readline().split())
lint = lambda :[int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda: sys.stdin.readline().strip('\n')
grid = lambda  r :[lint() for i in range(r)]
stpr = lambda x : sys.stdout.write(f'{x}' + '\n')
star = lambda x: print(' '.join(map(str, x)))

localsys = 0
start_time = time.time()
if (path.exists('input.txt')):
	sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
#left shift --- num*(2**k) --(k - shift)
# input = sys.stdin.readline
def p(n):
	d = defaultdict(int)
	while n % 2 == 0:
		n//=2
		d[2]+=1
	for i in range(3 ,int(n**0.5)+1,2):
		while n % i == 0:
			d[i]+=1
			n//=i
	if n > 1:
		d[n]+=1
	return d
n = I()
P = p(n)
print(n//min(P))





if localsys:
	print("\n\nTime Elased :",time.time() - start_time,"seconds")


