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;
long long P(long long m, long long n);
long long pi(long long x);
long long phi(long long m, long long n);
bool isprm[400005];
int cntprm[400005];
vector<long long> prm;
void Init() {
  for (int i = 2; i <= 400000; ++i) {
    isprm[i] = true;
  }
  for (int i = 2; i <= 400000; ++i) {
    cntprm[i] = cntprm[i - 1] + isprm[i];
    if (isprm[i]) {
      prm.push_back(i);
      for (int j = i + i; j <= 400000; j += i) isprm[j] = false;
    }
  }
}
long long sol(long long x) {
  long long ans = 0;
  long long sq = sqrt(x);
  for (int i = 0; i < (int)prm.size() && prm[i] <= sq; ++i) {
    long long a = prm[i], b = x / a;
    if (b <= 400000)
      ans += cntprm[b] - cntprm[a];
    else {
      ans += pi(b) - cntprm[a];
    }
  }
  return ans;
}
int main(void) {
  long long n;
  Init();
  cin >> n;
  cout << cntprm[(int)cbrt(n)] + sol(n) << "\n";
}
long long phi(long long m, long long n) {
  if (m) {
    if (n) {
      if (m <= prm[n - 1])
        return 1;
      else {
        if (prm[n - 1] * prm[n - 1] >= m)
          return pi(m) - n + 1;
        else
          return phi(m, n - 1) - phi(m / prm[n - 1], n - 1);
      }
    } else {
      return m;
    }
  } else {
    return 0;
  }
}
long long P(long long m, long long n) {
  long long res = 0, sq = sqrt(m);
  for (int i = n; i < (int)prm.size() && prm[i] <= sq; ++i) {
    auto num = prm[i];
    res += pi(m / num) - pi(num) + 1;
  }
  return res;
}
long long pi(long long x) {
  if (x <= 400000)
    return cntprm[x];
  else {
    long long n = pi(ceil(cbrt(x))), m = x;
    return phi(m, n) + n - 1 - P(m, n);
  }
}