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;
    }
  }
}
vector<long long int> lo, hi;
long long int m;
long long int pi_0(long long int N) {
  m = sqrt(N);
  vector<long long int> values;
  lo.resize(m + 1), hi.resize(m + 1);
  auto at = [&](long long int x) -> long long int& {
    if (x <= m) return lo[x];
    return hi[N / x];
  };
  for (int i = 1; i <= m; ++i) {
    values.push_back(i);
    if (N / i != i) values.push_back(N / i);
  }
  sort(values.begin(), values.end(), greater<long long int>());
  for (long long int n : values) {
    at(n) = n - 1;
  }
  for (long long int p : primes) {
    if (p > m) break;
    for (long long int n : values) {
      if (n < p * p) break;
      at(n) -= (at(n / p) - at(p - 1));
    }
  }
  return at(N);
}
vector<long long int> pref(MAX);
void buildPref() {
  for (long long int i = 1; i < MAX; i++) {
    pref[i] += (isPrime[i] + pref[i - 1]);
  }
}
int main() {
  ;
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  primesSieve(MAX);
  long long int n;
  cin >> n;
  pi_0(n);
  auto at = [&](long long int x) -> long long int& {
    if (x <= m) return lo[x];
    return hi[n / x];
  };
  long long int res = 0;
  long long int l = (int)floor(cbrtl(n));
  res += at(l);
  for (auto p : primes) {
    if (p * p > n) break;
    long long int aux = n / p;
    long long int countD = 0, countP = 0;
    res += (at(n / p) - at(p));
  }
  cout << res << "\n";
  return 0;
}