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 long long int MOD = 1e9 + 7;
const long long int MAX = 320000;
vector<long long int> primes;
vector<bool> isPrime;
void primesSieve(int n) {
  isPrime.resize(n + 1, true);
  isPrime[0] = isPrime[1] = false;
  primes.push_back(2);
  for (int i = 4; i <= n; i += 2) isPrime[i] = false;
  for (long long int i = 3; i <= n; i += 2) {
    if (isPrime[i]) {
      primes.push_back(i);
      if (i * i <= n)
        for (long long int j = i * i; j <= n; j += 2 * i) isPrime[j] = false;
    }
  }
}
long long int r, ndr, nv, n;
long long int check(long long int v) {
  return v >= ndr ? (n / v - 1) : (nv - v);
}
vector<long long int> S;
vector<long long int> V;
long long int pi_0(long long int n) {
  r = (long long int)sqrt(n);
  ndr = n / r;
  nv = r + ndr - 1;
  S.resize(nv + 1);
  V.resize(nv + 1);
  for (long long int i = 0; i < r; i++) {
    V[i] = n / (i + 1);
  }
  for (long long int i = r; i < nv; i++) {
    V[i] = V[i - 1] - 1;
  }
  for (long long int i = 0; i < nv; i++) {
    S[i] = V[i] - 1;
  }
  for (long long int p = 2; p <= r; p++) {
    if (S[nv - p] > S[nv - p + 1]) {
      long long int sp = S[nv - p + 1];
      long long int p2 = p * p;
      for (long long int i = 0; i < nv; i++) {
        if (V[i] >= p2) {
          S[i] -= 1LL * (S[check(V[i] / p)] - sp);
        } else
          break;
      }
    }
  }
  long long int ans = S[0];
  return ans;
}
int main() {
  ;
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  primesSieve(MAX);
  cin >> n;
  pi_0(n);
  long long int res = 0;
  long long int l = (int)floor(cbrtl(n));
  res += S[check(l)];
  for (auto p : primes) {
    if (p * p > n) break;
    long long int aux = n / p;
    long long int countD = 0, countP = 0;
    res += (S[check(n / p)] - S[check(p)]);
  }
  cout << res << "\n";
  return 0;
}