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 <class T1, class T2, class T3 = hash<T1>>
using umap = unordered_map<T1, T2, T3>;
template <class T>
using uset = unordered_set<T>;
template <class T>
using vec = vector<T>;
const long long infll = numeric_limits<long long>::max() >> 1;
const long long inf = numeric_limits<long long>::max() >> 1;
const long long N = 1e7 + 1;
const long long M = 1e6 + 1;
const long long A = 1e4 + 1;
const long long B = 1e2 + 1;
long long n, cur, ans;
long long lp[N];
long long ph[N];
long long pc[N];
long long pr[M];
long long mem[A][B];
void sieve() {
  for (long long i = 2; i < N; ++i) {
    if (!lp[i]) {
      lp[i] = pr[++cur] = i;
      ph[i] = i - 1;
    }
    for (long long j = 1; j <= cur && pr[j] <= lp[i] && pr[j] * i < N; ++j) {
      if (lp[i] == pr[j]) {
        ph[i * pr[j]] = ph[i] * pr[j];
      } else {
        ph[i * pr[j]] = ph[i] * (pr[j] - 1);
      }
      lp[i * pr[j]] = pr[j];
    }
    pc[i] = cur;
  }
}
long long p2(long long, long long);
long long phi(long long m, long long n) {
  if (m < A && n < B && mem[m][n] != -1) return mem[m][n];
  if (n == 0) return m;
  if (pr[n] >= m) return 1;
  long long ret = phi(m, n - 1) - phi(m / pr[n], n - 1);
  if (m < A && n < B) mem[m][n] = ret;
  return ret;
}
long long pi(long long m) {
  if (m < N) return pc[m];
  long long n = pi(cbrt(m));
  return phi(m, n) + n - 1 - p2(m, n);
}
long long p2(long long m, long long n) {
  long long ret = 0;
  long long lim = sqrt(m);
  for (int i = n + 1; pr[i] <= lim; ++i) ret += pi(m / pr[i]) - pi(pr[i]) + 1;
  return ret;
}
void input() { cin >> n; }
void solve() {
  memset(mem, -1, sizeof mem);
  ans += pi(cbrt(n));
  for (int i = 1; i <= cur; ++i) {
    if (1ll * pr[i] * pr[i] > n) {
      break;
    }
    ans += pi(n / pr[i]) - i;
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  sieve();
  input();
  solve();
}