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>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
using vi = vector<int>;
using vl = vector<long long>;
using vd = vector<double>;
using vs = vector<string>;
using vld = vector<long double>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;
using vpd = vector<pair<double, double>>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
const ll MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
int cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
template <class A>
void re(complex<A>& c);
template <class A, class B>
void re(pair<A, B>& p);
template <class A>
void re(vector<A>& v);
template <class A, size_t SZ>
void re(array<A, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& d) {
  str t;
  re(t);
  d = stod(t);
}
void re(long double& d) {
  str t;
  re(t);
  d = stold(t);
}
template <class H, class... T>
void re(H& h, T&... t) {
  re(h);
  re(t...);
}
template <class A>
void re(complex<A>& c) {
  A a, b;
  re(a, b);
  c = {a, b};
}
template <class A, class B>
void re(pair<A, B>& p) {
  re(p.first, p.second);
}
template <class A>
void re(vector<A>& x) {
  for (auto& a : x) re(a);
}
template <class A, size_t SZ>
void re(array<A, SZ>& x) {
  for (auto& a : x) re(a);
}
void setIO(string second) {
  freopen((second + ".in").c_str(), "r", stdin);
  freopen((second + ".out").c_str(), "w", stdout);
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return (a / (gcd(a, b)) * b); }
ll power(ll a, ll b) {
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = ((res * a) % MOD);
    a = ((a * a) % MOD);
    b >>= 1;
  }
  return res;
}
ll get(ll n) {
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return i;
    }
  }
  return n;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  re(n);
  cout << 1 + ((n - get(n)) / 2) << "\n";
}
