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;
using lli = long long int;
vector<int> sieve(int n) {
  vector<int> primes;
  vector<bool> is(n + 1, true);
  for (int i = 2; i <= n; ++i) {
    if (is[i]) primes.push_back(i);
    for (int p : primes) {
      int d = i * p;
      if (d > n) break;
      is[d] = false;
      if (i % p == 0) break;
    }
  }
  return primes;
}
const int M = 1e6;
const vector<int> primes = sieve(M);
lli SumPrimePi(lli n) {
  lli v = sqrt(n), p, temp, q, j, end, i, d;
  vector<lli> lo(v + 2), hi(v + 2);
  vector<bool> used(v + 2);
  for (p = 1; p <= v; p++) {
    lo[p] = p - 1;
    hi[p] = n / p - 1;
  }
  for (p = 2; p <= v; p++) {
    if (lo[p] == lo[p - 1]) continue;
    temp = lo[p - 1];
    q = p * p;
    hi[1] -= hi[p] - temp;
    j = 1 + (p & 1);
    end = (v <= n / q) ? v : n / q;
    for (i = p + j; i <= 1 + end; i += j) {
      if (used[i]) continue;
      d = i * p;
      if (d <= v)
        hi[i] -= hi[d] - temp;
      else
        hi[i] -= lo[n / d] - temp;
    }
    if (q <= v)
      for (i = q; i <= end; i += p * j) used[i] = true;
    for (i = v; i >= q; i--) {
      lo[i] -= lo[i / p] - temp;
    }
  }
  return hi[1];
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  lli n;
  cin >> n;
  int l = (int)floor(cbrtl(n));
  lli ans = SumPrimePi(l);
  l = (int)floor(sqrtl(n));
  for (int p : primes) {
    if (p > l) break;
    ans += SumPrimePi(n / p) - SumPrimePi(p);
  }
  cout << ans << "\n";
  return 0;
}