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 pr() {}
template <typename H, typename... T>
void pr(H var1, T... var2) {
  cout << fixed << setprecision(10) << var1 << "\n";
  pr(var2...);
}
void ps() {}
template <typename H, typename... T>
void ps(H var1, T... var2) {
  cout << fixed << setprecision(10) << var1 << ' ';
  ps(var2...);
}
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;
}
using u64 = long long;
using u128 = long long;
u64 binpower(u64 base, u64 e, u64 mod) {
  u64 result = 1;
  base %= mod;
  while (e) {
    if (e & 1) result = (u128)result * base % mod;
    base = (u128)base * base % mod;
    e >>= 1;
  }
  return result;
}
bool check_composite(u64 n, u64 a, u64 d, int second) {
  u64 x = binpower(a, d, n);
  if (x == 1 || x == n - 1) return false;
  for (int r = 1; r < second; r++) {
    x = (u128)x * x % n;
    if (x == n - 1) return false;
  }
  return true;
};
bool MillerRabin(u64 n, int iter = 5) {
  if (n < 4) return n == 2 || n == 3;
  int second = 0;
  u64 d = n - 1;
  while ((d & 1) == 0) {
    d >>= 1;
    second++;
  }
  for (int i = 0; i < iter; i++) {
    int a = 2 + rand() % (n - 3);
    if (check_composite(n, a, d, second)) return false;
  }
  return true;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  re(n);
  if (MillerRabin(n)) {
    cout << 1 << "\n";
  } else {
    for (int i = 2; i <= n; i++) {
      if (n % i == 0) {
        cout << n / i << "\n";
        return 0;
      }
    }
  }
}
