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;
struct pi_func {
  int low_N, low_K;
  vector<vector<long long> > dp;
  vector<bool> sieve;
  vector<int> last_prime;
  vector<long long> primes;
  int limit = 1000000;
  void precalc(int _n, int _k, int _limit = 1000000) {
    long long i, j;
    low_N = _n;
    low_K = _k;
    limit = _limit;
    dp = vector<vector<long long> >(low_N + 3, vector<long long>(low_K + 3, 0));
    primes.clear();
    sieve = vector<bool>(limit + 3, false);
    last_prime = vector<int>(limit + 3, 0);
    for (i = 2; i <= limit; i++) {
      last_prime[i] = last_prime[i - 1];
      if (sieve[i]) continue;
      last_prime[i]++;
      primes.push_back(i);
      for (j = i * i; j <= limit; j += i) sieve[j] = true;
    }
    if (primes.size() < low_K) {
      cerr << "low_K is too big..";
      exit(0);
    }
    for (i = 1; i <= low_N; i++) {
      dp[i][1] = i;
      for (j = 2; j <= low_K; j++)
        dp[i][j] = dp[i][j - 1] - dp[i / primes[j - 2]][j - 1];
    }
  }
  long long compute(long long n, long long k) {
    if (n < primes[k - 1]) return 1;
    if (k == 1) return n;
    if (n <= low_N && k <= low_K) return dp[n][k];
    return compute(n, k - 1) - compute(n / primes[k - 2], k - 1);
  }
  long long Lehmer(long long n) {
    if (n <= limit) return last_prime[n] + 1;
    int r2 = sqrt(n);
    int r3 = cbrt(n);
    int pos = last_prime[r3] + 1;
    long long ans = compute(n, pos) + pos - 1;
    for (int i = pos; primes[i - 1] <= r2; i++)
      ans -= Lehmer(n / primes[i - 1]) - i;
    return ans;
  }
  long long pi(long long n) {
    long long sq = sqrt(n);
    int pos = last_prime[sq] + 1;
    return compute(n, pos) + pos - 1;
  }
};
long long n, i;
pi_func L;
long long ans;
int main() {
  L.precalc(100000, 100);
  scanf("%lld", &n);
  int cnt = 1;
  for (auto e : L.primes) {
    if (1LL * e * e * e <= n) ans++;
    if (1LL * e * e > n) break;
    ans += L.Lehmer(n / e) - (++cnt);
  }
  printf("%lld", ans);
  return 0;
}