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>
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x + _y;
  if (_ >= _mod) _ -= _mod;
  return _;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x - _y;
  if (_ < 0) _ += _mod;
  return _;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007ll) {
  long long _ = _x * _y;
  if (_ >= _mod) _ %= _mod;
  return _;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1ll;
  long long _tmp = mypow(_a, _x / 2, _mod);
  _tmp = mul(_tmp, _tmp, _mod);
  if (_x & 1) _tmp = mul(_tmp, _a, _mod);
  return _tmp;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0ll;
  long long _tmp = mymul(_a, _x / 2, _mod);
  _tmp = add(_tmp, _tmp, _mod);
  if (_x & 1) _tmp = add(_tmp, _a, _mod);
  return _tmp;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
bool p[1000000 + 1000000];
int ck[2500000], psum[1000000];
vector<long long> pset;
void build() {
  for (int i = 2; i < 1000000; i++)
    if (!p[i]) {
      psum[i]++;
      pset.push_back(i);
      for (int j = 1000000 / i; j >= i; j--) p[i * j] = true;
    }
  for (int i = 3; i < 1000000; i++) psum[i] += psum[i - 1];
  int nk = 0;
  for (long long i = 2; i < 2500000; i++) {
    while (pset[nk] * pset[nk] <= i) nk++;
    ck[i] = nk;
  }
}
long long n, ans;
inline int Pi(long long);
long long DP(long long x, long long k) {
  if (x <= 0) return 0;
  if (k == 0) return x;
  if (pset[k - 1] * pset[k - 1] >= x) return Pi(x) - k + 1;
  return DP(x, k - 1) - DP(x / pset[k - 1], k - 1);
}
inline int Pi(long long x) {
  if (x < 1000000) return psum[x];
  long long x3 = 1, x2 = 1;
  while (x3 * x3 * x3 <= x) x3++;
  while (x2 * x2 <= x) x2++;
  x2--;
  x3--;
  long long tsum = 0;
  for (long long i = x3 + 1; i <= x2; i++)
    if (!p[i]) tsum += Pi(x / i) - Pi(i) + 1;
  return DP(x, psum[x3]) + psum[x3] - 1 - tsum;
}
void init() { n = getint(); }
void solve() {
  for (size_t i = 0; i < pset.size(); i++) {
    if (pset[i] * pset[i] * pset[i] > n) break;
    ans++;
  }
  for (size_t i = 0; i < pset.size(); i++) {
    if (pset[i] * pset[i] >= n) break;
    ans += Pi(n / pset[i]) - Pi(pset[i]);
  }
  printf("%lld\n", ans);
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}