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;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
inline int rt2(const long long &first) {
  int tmp = sqrt(first) + 2;
  while ((long long)tmp * tmp > first) --tmp;
  return tmp;
}
const int max0 = 1000000, max1 = 700000;
long long l, r;
long long val[max0 + 5];
int N, sqrtn;
long long n;
inline int get_id(const long long &first) {
  return first > sqrtn ? N - (n / first) : first - 1;
}
int rtp[max0 + 5];
long long cnt[max0 + 5];
int cntp[max1 + 5];
bool isp[max1 + 5];
int pr[max1 + 5];
int pn = 0;
int lim0, lim1;
int lim2[max1 + 5];
inline void prepare() {
  memset(val, 0, sizeof val);
  memset(isp, 1, sizeof isp);
  isp[1] = 0;
  pn = 0;
  for (int i = 2; i <= max1; ++i) {
    if (isp[i]) {
      pr[pn++] = i;
      for (int j = i; j <= max1; j += i) isp[j] = 0;
    }
    cntp[i] = pn;
  }
}
int main() {
  prepare();
  scanf("%I64d", &n);
  sqrtn = rt2(n);
  N = 0;
  for (long long i = 1; i <= n; i = n / val[N++] + 1) val[N] = n / i;
  reverse(val, val + N);
  int now = 0;
  lim0 = sqrtn, lim1 = cntp[lim0];
  for (int i = (0), _end_ = (N); i < _end_; ++i)
    rtp[i] = cntp[rt2(val[i])], lim2[i] = cntp[min((long long)lim0, val[i])];
  for (int i = (0), _end_ = (N); i < _end_; ++i) cnt[i] = val[i];
  for (int i = (0), _end_ = (lim1); i < _end_; ++i) {
    while (now < N && i >= rtp[now]) ++now;
    for (int j = N - 1; j >= now; --j) {
      int k = get_id(val[j] / pr[i]);
      cnt[j] -= cnt[k] - max(0, i - rtp[k]);
    }
  }
  for (int i = (0), _end_ = (N); i < _end_; ++i)
    cnt[i] -= max(0, lim2[i] - rtp[i]);
  long long ret = 0;
  for (int i = (0), _end_ = (lim1); i < _end_; ++i)
    if ((long long)pr[i] * pr[i] * pr[i] <= n)
      ++ret;
    else
      break;
  for (int i = (0), _end_ = (lim1); i < _end_; ++i) {
    ret += (cnt[get_id(n / pr[i])] - 1);
    ret += lim1 - i - 1;
  }
  printf("%I64d\n", ret);
  return 0;
}