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 MOD = 1000000007;
const int msqn = 316300;
bool isc[msqn + 5];
int primes[27300];
int prc, c;
void sieve(int M) {
  isc[0] = isc[1] = 1;
  for (int i = (2); i < (M + 1); i++) {
    if (!isc[i]) primes[++prc] = i;
    if (!(i & 1) && (i << 1) <= M) {
      isc[i << 1] = 1;
      continue;
    }
    for (register int j = 1; j <= prc; j += 5) {
      if (primes[j] * i > M + 1) break;
      isc[primes[j] * i] = 1;
      if (!(i % primes[j]) || !primes[j + 1] || (primes[j + 1] * i > M + 1))
        break;
      isc[primes[j + 1] * i] = 1;
      if (!(i % primes[j + 1]) || !primes[j + 2] || (primes[j + 2] * i > M + 1))
        break;
      isc[primes[j + 2] * i] = 1;
      if (!(i % primes[j + 2]) || !primes[j + 3] || (primes[j + 3] * i > M + 1))
        break;
      isc[primes[j + 3] * i] = 1;
      if (!(i % primes[j + 3]) || !primes[j + 4] || (primes[j + 4] * i > M + 1))
        break;
      isc[primes[j + 4] * i] = 1;
    }
  }
}
namespace PCF {
long long ans[2 * msqn + 5], ind1[2 * msqn + 5], ind2[2 * msqn + 5],
    w[2 * msqn + 5], tot = 0, sqr, NN;
void init(long long n) {
  sqr = sqrt(n);
  tot = 0;
  for (long long l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    w[++tot] = n / l;
    ans[tot] = w[tot] - 1;
    if (n / l <= sqr)
      ind1[n / l] = tot;
    else
      ind2[r] = tot;
  }
  for (int i = (1); i < ((prc) + 1); i++)
    for (int j = 1; j <= tot && 1ll * primes[i] * primes[i] <= w[j]; j++) {
      long long v = w[j] / primes[i];
      long long k = (v <= sqr) ? ind1[v] : ind2[n / v];
      ans[j] -= ans[k] - (i - 1);
    }
  NN = n;
}
long long cnt(long long n) {
  return (n <= sqr) ? ans[ind1[n]] : ans[ind2[NN / n]];
}
}  // namespace PCF
long long cnt(long long n) { return PCF::cnt(n); }
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  sieve(msqn);
  long long n;
  cin >> n;
  long long cbrt = 1, ans = 0;
  while ((cbrt + 1) * (cbrt + 1) * (cbrt + 1) <= n) {
    cbrt++;
    if (!isc[cbrt]) ans++;
  }
  PCF::init(n);
  for (int i = (1); i < ((prc) + 1); i++) {
    if (n / primes[i] > primes[i]) ans += cnt(n / primes[i]) - i;
  }
  cout << ans << endl;
}