You are given an integer number $n$. The following algorithm is applied to it:

  if $n = 0$, then end algorithm;  find the smallest prime divisor $d$ of $n$;  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 \le n \le 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.

Difficulty: interview

Starter code:

Solutions:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)

if N%2==0:
    print(N//2)
    return

for i in range(2,110000):
    if N%i==0:
        print( (N-i)//2 +1)
        return

print(1)




import math
n = int(input())
d = 0
for i in range(2,int(math.sqrt(n))+1):
    if n%i == 0:
        d = i
        break
if d == 0:
    d = n
if d == 2:
    print(n//d)
else:
    print(1+(n-d)//2)


n = int(input())
if n % 2 == 0:
    print(n // 2)
    return

for x in range(2, int(n**0.5 + 1)):
    if n % x == 0:
        print(1 + (n - x) // 2)
        return
print(1)


n=int(input())
ans=0
if n%2!=0:
   i=3
   while n%i!=0 and i*i<n:i+=2
   if n%i!=0:i=n
   n-=i
   ans=1
ans+=n//2
print(ans)

n = int(input())
i = 2
m = 0
while n%i!=0 and i*i<=n:
    i+=1
if n%i==0:
    m+=1
    n-=i
    m+=n//2
    print(m)
else:
    print(1)


n=int(input())
c=0
for i in range(2,int(n**0.5+1)):
    if n%i==0:
        c=1
        break
if c==0:print(1)
else:print((n-i)//2+1)

n=int(input())
count=0
while n!=0:
    if n%2==0:
       count+=n//2
       break
    flag=0
    for i in range(2,int(n**(0.5)+100)):
        if n%i==0:
            flag=1 
            break
    count+=1
    if flag==0:
        break
    else:
        n-=i
print(count)

import math
import sys
n = int(input())

for i in range(2,int(math.sqrt(n)) + 1):
    if n%i == 0:
        print(int((n - i)/2 + 1))
        return
print(1)


n=int(input())
if(n%2==0):
    print(n//2)
else:
    lp=n
    i=2
    while(i*i<=n):
        if(n%i==0):
            lp=i
            break
        i+=1
    print((n-lp)//2+1)


'''
////////////////      //////        ///////      //             ///////     //  //   //
////          //    ///   ///     ///    ///     //            ///  ///     ////     //
////    ////       ///     ///   ///      ///    //           /////////     ////     ///////
////     /////    ///       /// ///        ///   //          ///    ///     ////     //   //
//////////////     ///////////   ///////////     //////     ///     ///     //  //   //   //
'''



import math

n = int(input())

subs = 0

while(n > 0):
  if (n % 2 == 0):
    subs += n // 2
    n = 0
  else:
    sq = int(math.sqrt(n))
    found = False
    for i in range(2, sq + 1):
      if (n % i) == 0:
        found = True
        break

    if found:
      subs += 1
      n -= i
    else:
      subs += 1
      n = 0

print(subs)

import math
def find(n):
    if n==2:
        return 2
    for i in range(2,int(math.sqrt(n))+2):
        if n%i==0:
            return i
    return n
n=int(input())
ans=0
fro=2
while n>0:
    if n%2==0:
        ans+=n//2
        break
    f=find(n)
    ans+=1
    n-=f
print(ans)


n = int(input())

for i in range(2, n + 1):
    if n % i == 0:
        if i == 2:
            print(n // i)
            return
        else:
            print(1 + (n - i) // 2)
            return
    if i * i > n * 2:
        break

print(1 if n > 0 else 0)


def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())
MX = 10 ** 5

n = ii()
if n % 2 == 0:
    ans = n // 2
else:
    c = 3
    ans = 0
    while c <= MX:
        if n % c == 0:
            n -= c
            ans += 1
            break
        c += 1
    if ans:
        ans += n // 2
    else:
        ans = 1
print(ans)

x = int(input())
for a in range(2, 10**6):
    if (x % a == 0):
        print(1 + (x - a) // 2)
        return
print(1)

from math import sqrt,ceil
def f(n):
	for i in range(2,int(sqrt(n))+2):
		if n%i==0:
			return i
	return n


n = int(input())
cnt = 0

while n%2!=0:
	n -= f(n)
	cnt+=1
print(cnt+n//2)


def is_prime(n):
    for i in range(2, int(n**0.5)+1):
        if not n%i:
            return False
    return True

n=int(input())
c=0
while True:
    if n%2==0:
        c+=n//2
        break
    if is_prime(n):
        c+=1
        break
    for i in range(2,n):
        if is_prime(i) and n%i==0:
            break
    n-=i
    c+=1
    if n==0:
        break
print(c)

n=int(input())

import math
import sys

if n%2==0:
    print(n//2)
    return



xn=math.ceil(math.sqrt(n))
for i in range(2,xn+2):
    if n%i==0:
        print((n-i)//2+1)
        return
        

print(1)


from math import floor, sqrt
try: 
    int
except NameError: 
    long = int
 
def fac(n):
    step = lambda x: 1 + (x<<2) - ((x>>1)<<1)
    maxq = int(floor(sqrt(n)))
    d = 1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
        q = step(d)
        d += 1
    return q <= maxq and [q] + fac(n//q) or [n]
def _try_composite(a, d, n, s):
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2**i * d, n) == n-1:
            return False
    return True # n  is definitely composite
 
def is_prime(n, _precision_for_huge_n=16):
    if n in _known_primes or n in (0, 1):
        return True
    if any((n % p) == 0 for p in _known_primes):
        return False
    d, s = n - 1, 0
    while not d % 2:
        d, s = d >> 1, s + 1
    # Returns exact according to http://primes.utm.edu/prove/prove2_3.html
    if n < 1373653: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3))
    if n < 25326001: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5))
    if n < 118670087467: 
        if n == 3215031751: 
            return False
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7))
    if n < 2152302898747: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
    if n < 3474749660383: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
    if n < 341550071728321: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
    # otherwise
    return not any(_try_composite(a, d, n, s) 
                   for a in _known_primes[:_precision_for_huge_n])
 
_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]
 
n=int(input())
x=fac(n)[0]
if is_prime(n):
    print(1)
elif n%2==0:
    print(n//2)
else:
    print(((n-x)//2)+1)




import math
def find(n):
    if n==2:
        return 2
    for i in range(2,int(math.sqrt(n))+2):
        if n%i==0:
            return i
    return n
n=int(input())
lol=0
kek=2
while n>0:
    if n%2==0:
        lol+=n//2
        break
    f=find(n)
    lol+=1
    n-=f
print(lol)

import math
def primeFactors(n): 
    if(n%2==0):
        return 2   
    for i in range(3,int(math.sqrt(n))+1,2): 
        if(n % i== 0): 
            return i 
    if(n > 2): 
        return n 
           
n=int(input())
k=primeFactors(n)
if(k==2):
    print(n//k)
elif(k==n):
    print(1)
else:
    n-=k
    print(1+(n//2))

n = int(input())
if n % 2 == 0:
    print(n // 2)
else:
    i = 3
    while i <= n // i:
        if n % i == 0:
            n -= i
            print(1 + (n // 2))
            return
        i += 1
    print(1)


import sys
from math import ceil, sqrt

input = sys.stdin.readline

n = int(input())

if n % 2 == 0:
    print(int(n/2))
else:
    prime = n
    for i in range(2, ceil(sqrt(n)) + 1):
        if n % i == 0:
            prime = i
            break
    print(1 + int((n - prime)/2))

from math import sqrt
def kek(n):
    if n==2:
        return 2
    for i in range(2,int(sqrt(n))+2):
        if n%i==0:
            return i
    return n

n=int(input())
k=0
while n>0:
    if n%2==0:
        k+=n//2
        break
    k+=1
    n-=kek(n)
print(k)
    
    


from sys import stdin, stdout
from math import *

def nStep(n):
    if (n==0):
        return 0
    if (n==2):
        return 1
    for i in range(2,floor(sqrt(n)+2),1):
        if (n % i == 0):
            if (i==2):
                return floor(n/2)
            else:
                return 1+nStep(n - i)
    return 1
def main():
    n=int(stdin.readline())
    stdout.write(str(nStep(n)))
    return 0



def __starting_point():
    main()
__starting_point()

import math
def factors(k):
    L = []
    for i in range(2,int(math.sqrt(k))+1):
        if k % i == 0:
            if i == k//i:
                L.append(i)
            else:
                L.append(i)
                L.append(k//i)
    L.append(k)
    return L
    

def prime(p):
    for i in range(2,int(math.sqrt(p))+1):
        if p % i == 0:
            return 0
    return 1


n = int(input())
if n % 2 == 0:
    print(n//2)
else:
    a = factors(n)
    for i in a:
        if prime(i):
            print(((n-i)//2)+1)
            break