Problem: If an integer a is divisible by another integer b, then b is called the divisor of a.

For example: 12 has positive 6 divisors. They are 1, 2, 3, 4, 6 and 12.

Let’s define a function D(n) — number of integers between 1 and n (inclusive) which has exactly four positive divisors.

Between 1 and 10 only the integers 6, 8 and 10 has exactly four positive divisors. So, D(10) = 3.

You are given an integer n. You have to calculate D(n).

Input

The only line contains integer n (1 ≤ n ≤ 1011) — the parameter from the problem statement.

Output

Print the only integer c — the number of integers between 1 and n with exactly four divisors.

Examples

Input

10


Output

3


Input

20


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
template <class T1, class T2>
inline bool chmax(T1 &a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T1, class T2>
inline bool chmin(T1 &a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
const double EPS = 1e-9, PI = acos(-1);
const double pi = 3.141592653589793238462643383279;
template <int mod>
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
  static int get_mod() { return mod; }
};
using modint = ModInt<1000000007>;
template <typename T>
struct Combination {
  vector<T> _fact, _rfact, _inv;
  Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
    _fact[0] = _rfact[sz] = _inv[0] = 1;
    for (int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
    _rfact[sz] /= _fact[sz];
    for (int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
    for (int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
  }
  inline T fact(int k) const { return _fact[k]; }
  inline T rfact(int k) const { return _rfact[k]; }
  inline T inv(int k) const { return _inv[k]; }
  T P(int n, int r) const {
    if (r < 0 || n < r) return 0;
    return fact(n) * rfact(n - r);
  }
  T C(int p, int q) const {
    if (q < 0 || p < q) return 0;
    return fact(p) * rfact(q) * rfact(p - q);
  }
  T H(int n, int r) const {
    if (n < 0 || r < 0) return (0);
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};
long long GCD(long long a, long long b) { return (b == 0) ? a : GCD(b, a % b); }
long long LCM(long long a, long long b) { return a / GCD(a, b) * b; }
long long prime_pi(const long long n) {
  if (n <= 1) return 0;
  if (n == 2) return 1;
  const int sq = sqrtl(n);
  int s = 1 + sq >> 1;
  vector<int> smalls(s);
  for (int i = 1; i < s; ++i) smalls[i] = i;
  vector<int> roughs(s);
  for (int i = 0; i < s; ++i) roughs[i] = i << 1 | 1;
  vector<long long> larges(s);
  for (int i = 0; i < s; ++i) larges[i] = (n / (i << 1 | 1) - 1) >> 1;
  vector<bool> skip(sq + 1);
  const auto divide = [](long long n, long long d) -> int {
    return (long double)n / d;
  };
  const auto half = [](int n) -> int { return (n - 1) >> 1; };
  int pc = 0;
  for (int p = 3; p <= sq; p += 2)
    if (!skip[p]) {
      int q = p * p;
      if ((long long)q * q > n) break;
      skip[p] = true;
      for (int i = q; i <= sq; i += p << 1) skip[i] = true;
      int ns = 0;
      for (int k = 0; k < s; ++k) {
        int i = roughs[k];
        if (skip[i]) continue;
        long long d = (long long)i * p;
        larges[ns] = larges[k] -
                     (d <= sq ? larges[smalls[d >> 1] - pc]
                              : smalls[half(divide(n, d))]) +
                     pc;
        roughs[ns++] = i;
      }
      s = ns;
      for (int i = half(sq), j = ((sq / p) - 1) | 1; j >= p; j -= 2) {
        int c = smalls[j >> 1] - pc;
        for (int e = (j * p) >> 1; i >= e; --i) smalls[i] -= c;
      }
      ++pc;
    }
  larges[0] += (long long)(s + 2 * (pc - 1)) * (s - 1) / 2;
  for (int k = 1; k < s; ++k) larges[0] -= larges[k];
  for (int l = 1; l < s; ++l) {
    int q = roughs[l];
    long long m = n / q;
    int e = smalls[half(m / q)] - pc;
    if (e < l + 1) break;
    long long t = 0;
    for (int k = l + 1; k <= e; ++k) t += smalls[half(divide(m, roughs[k]))];
    larges[0] += t - (long long)(e - l) * (pc + l - 1);
  }
  return larges[0] + 1;
}
bool sieve[1010101];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  long long n;
  cin >> n;
  memset(sieve, true, sizeof(sieve));
  sieve[0] = sieve[1] = false;
  for (int i = 2; i * i <= 1000000; i++) {
    if (sieve[i]) {
      for (int j = i * 2; j <= 1000000; j += i) sieve[j] = false;
    }
  }
  vector<long long> primes;
  for (int i = 0; i < (int)1000001; ++i)
    if (sieve[i]) primes.push_back(i);
  long long ans = 0;
  for (int i = 0; i < primes.size(); i++) {
    long long t = prime_pi(n / primes[i]);
    if (t - (i + 1) <= 0) break;
    ans += t - (i + 1);
  }
  for (int i = 0; i < primes.size(); i++) {
    long long t = primes[i];
    if (t * t * t > n) break;
    ans++;
  }
  cout << ans << endl;
  return 0;
}