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.
#include <bits/stdc++.h>
template <class T>
T _abs(T n) {
  return (n < 0 ? -n : n);
}
template <class T>
T _max(T a, T b) {
  return (!(a < b) ? a : b);
}
template <class T>
T _min(T a, T b) {
  return (a < b ? a : b);
}
template <class T>
T sq(T x) {
  return x * x;
}
template <class T>
T gcd(T a, T b) {
  return (b != 0 ? gcd<T>(b, a % b) : a);
}
template <class T>
T lcm(T a, T b) {
  return (a / gcd<T>(a, b) * b);
}
template <class T>
bool inside(T a, T b, T c) {
  return a <= b && b <= c;
}
template <class T>
void setmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
void setmin(T &a, T b) {
  if (b < a) a = b;
}
int fx[] = {0, 0, -1, 1};
int fy[] = {1, -1, 0, 0};
using namespace std;
int prime[1000000];
void sieve() {
  prime[1] = 1;
  for (int i = 4; i <= 1000000; i += 2) {
    prime[i] = 1;
  }
  for (int i = 3; i * i <= 1000000; i += 2) {
    if (prime[i] == i) {
      for (int j = i * i; j <= 1000000; j += i) prime[j] = 1;
    }
  }
}
int main() {
  freopen("/Users/shahadat/Desktop/input.txt", "r", stdin);
  sieve();
  long long n;
  cin >> n;
  bool flag = true;
  for (long long i = 2; i * i <= n; i++) {
    if (prime[i] == 0 && n % i == 0) {
      n -= i;
      flag = false;
      break;
    }
  }
  if (flag) n = 0;
  long long res = n / 2 + 1;
  cout << res << endl;
}
