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;
const int maxp = 7, maxpm = 2 * 3 * 5 * 7 * 11 * 13 * 17, maxx = 5e6;
int phi[maxpm + 1][maxp + 1], p[maxp + 1], sp[maxx], cachepi[maxx],
    primes[maxx], sz = 0;
int sqrt2(long long x) {
  long long r = (long long)sqrt(x - 0.1);
  while (r * r <= x) ++r;
  return int(r - 1);
}
int sqrt3(long long x) {
  long long r = (long long)cbrt(x - 0.1);
  while (r * r * r <= x) ++r;
  return int(r - 1);
}
void init() {
  for (int i = 2; i < maxx; i++) {
    if (!sp[i]) sp[i] = i, primes[++sz] = i;
    cachepi[i] = sz;
    for (int j = 1; j <= sz && 1LL * i * primes[j] < maxx && primes[j] <= sp[i];
         j++) {
      sp[i * primes[j]] = primes[j];
      if (i % primes[j] == 0) break;
    }
  }
  p[0] = 1;
  for (int i = 0; i <= maxpm; i++) phi[i][0] = i;
  for (int j = 1; j <= maxp; j++) {
    p[j] = p[j - 1] * primes[j];
    for (int i = 0; i <= maxpm; i++)
      phi[i][j] = phi[i][j - 1] - phi[i / primes[j]][j - 1];
  }
}
long long PHI(long long x, int a) {
  if (a == 0) return x;
  if (a <= maxp) return phi[x % p[a]][a] + (long long)(x / p[a]) * phi[p[a]][a];
  if (1LL * primes[a] * primes[a] >= x) return cachepi[x] - a + 1;
  if (1LL * primes[a] * primes[a] * primes[a] >= x && x < maxx) {
    int li = cachepi[sqrt2(x)];
    long long ret = cachepi[x] - 1LL * (li - a + 1) * (li + a - 2) / 2;
    for (int i = a + 1; i <= li; i++) ret += cachepi[x / primes[i]];
    return ret;
  }
  return PHI(x, a - 1) - PHI(x / primes[a], a - 1);
}
long long lehmer(long long x) {
  if (x < maxx) return cachepi[x];
  int a = cachepi[sqrt2(sqrt2(x))], b = cachepi[sqrt2(x)],
      c = cachepi[sqrt3(x)];
  long long ret = PHI(x, a) + (long long)(b + a - 2) * (b - a + 1) / 2;
  for (int i = a + 1; i <= b; i++) {
    long long xpi = x / primes[i];
    ret -= lehmer(xpi);
    if (i <= c) {
      long long li = cachepi[sqrt2(xpi)];
      for (int j = i; j <= li; j++) ret -= cachepi[xpi / primes[j]] - (j - 1);
    }
  }
  return ret;
}
int main() {
  init();
  long long n, ret = 0;
  scanf("%lld", &n);
  for (int i = 1; 1LL * primes[i] * primes[i] * primes[i] <= n; i++) ++ret;
  for (int i = 1; 1LL * primes[i] * primes[i] < n; ++i)
    ret += lehmer(n / primes[i]) - i;
  printf("%lld\n", ret);
}