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.
#!/usr/bin/env python3
from typing import Dict, List, Tuple


def input_lst() -> List[int]:
    return [int(x) for x in input().split()]

def print_out(res: List[int]):
    print(' '.join([str(x) for x in res]))

# def eratosthenes(n):     # n - число, до которого хотим найти простые числа
#

def main():

    n,  = (int(x) for x in input().split())
    sieve = list(range(int(n**0.5) + 1))

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

    sieve[1] = 0    # без этой строки итоговый список будет содержать единицу
    for i in sieve:
        if i > 1:
            if n/i == n//i:
                print((n - i)//2 + 1)
                return
            for j in range(i + i, len(sieve), i):
                sieve[j] = 0

    print(1)




if __name__ == '__main__':
    main()
