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;
template <typename T>
using maxHeap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
using minHeap = priority_queue<T, vector<T>, greater<T>>;
template <typename Iter>
ostream& _out(ostream& s, Iter b, Iter e) {
  s << "[";
  for (auto it = b; it != e; it++) s << (it == b ? "" : " ") << *it;
  s << "]";
  return s;
}
template <typename A, typename B>
ostream& operator<<(ostream& s, const pair<A, B>& p) {
  return s << "(" << p.first << "," << p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& s, const vector<T>& c) {
  return _out(s, begin(c), end(c));
}
bool debug = 0;
template <typename T>
void DEBUG(const T& x) {
  if (debug) cerr << x;
}
template <typename T, typename... Args>
void DEBUG(const T& head, const Args&... tail) {
  if (debug) {
    cerr << head;
    DEBUG(tail...);
  }
}
static constexpr int N = 1000000 + 5;
int64_t pi[N];
vector<int> primes;
bool sieved[N];
int64_t cube_root(int64_t x) {
  int64_t s = static_cast<int64_t>(cbrt(x - static_cast<long double>(0.1)));
  while (s * s * s <= x) ++s;
  return s - 1;
}
int64_t square_root(int64_t x) {
  int64_t s = static_cast<int64_t>(sqrt(x - static_cast<long double>(0.1)));
  while (s * s <= x) ++s;
  return s - 1;
}
void init() {
  primes.reserve(N);
  primes.push_back(1);
  for (int i = 2; i < N; i++) {
    if (!sieved[i]) primes.push_back(i);
    pi[i] = !sieved[i] + pi[i - 1];
    for (int p : primes)
      if (p > 1) {
        if (p * i >= N) break;
        sieved[p * i] = true;
        if (p % i == 0) break;
      }
  }
}
int64_t phi(int64_t m, int64_t n) {
  static constexpr int MM = 70000, NN = 400;
  static int64_t val[MM][NN];
  if (m < MM and n < NN and val[m][n]) return val[m][n] - 1;
  if (n == 0) return m;
  if (primes[n] >= m) return 1;
  int64_t ret = phi(m, n - 1) - phi(m / primes[n], n - 1);
  if (m < MM and n < NN) val[m][n] = ret + 1;
  return ret;
}
int64_t pi_count(int64_t);
int64_t P2(int64_t m, int64_t n) {
  int64_t sm = square_root(m), ret = 0;
  for (int64_t i = n + 1; primes[i] <= sm; i++)
    ret += pi_count(m / primes[i]) - pi_count(primes[i]) + 1;
  return ret;
}
int64_t pi_count(int64_t m) {
  if (m < N) return pi[m];
  int64_t n = pi_count(cube_root(m));
  return phi(m, n) + n - 1 - P2(m, n);
}
int main(int argc, char* argv[]) {
  if (argc > 1 and string(argv[1]) == "-D") debug = 1;
  if (!debug) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  }
  init();
  int64_t n, ans = 0;
  cin >> n;
  for (int i = 1; 1LL * primes[i] * primes[i] <= n; i++) {
    ans += pi_count(n / primes[i]) - i;
    if (1LL * primes[i] * primes[i] * primes[i] <= n) ans++;
  }
  cout << ans << '\n';
  return 0;
}