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, stdout
import math
from functools import reduce
import statistics
import numpy as np
import itertools
import operator
from sys import stdin, stdout
import math
from functools import reduce
import statistics
import numpy as np
import itertools
import sys
import operator
from collections import Counter
import decimal
sys.setrecursionlimit(10 ** 6 + 1)
"""
from time import time
import os
import sys
from io import BytesIO, IOBase
from collections import *
from bisect import *
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def prog_name():
    n = int(input())
    cnt = 0
    while n > 0:
        if n % 2 == 0:
            cnt += n // 2
            n = 0
        else:
            a = 0
            i = 3
            while i * i <= n:
                if n % i == 0:
                    a += 1
                    n -= i
                    break
                i += 2
            if a == 0:
                n -= n
            cnt += 1
    print(cnt)

    # print()
def main ():
    # init = time()
    # T = int(input())
    T = 1
    for unique in range(T):
        # print("Case #"+str(unique+1)+":",end = " ")
        prog_name()
    # print(time() - init)


if __name__ == "__main__":
    main()