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.
n = int(raw_input())

def prime(n):
  j = 2
  while j*j <= n: 
    if n % j == 0:
      return j
    j+=1
  return n
  

cont = 0

if n%2 != 0:
  n -= prime(n)
  cont += 1

print cont+(n/2)
   		  		    				 	    		     	