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 int MAX = 2e6 + 5;
const int M = 7;
int prime[MAX], how[MAX];
vector<int> v;
long long int pi(long long int m);
int phi[MAX + 1][M + 1], sz[M + 1];
int sqrt2(long long x) {
  long long r = sqrt(x - 0.1);
  while (r * r <= x) ++r;
  return r - 1;
}
long long int lehmer(long long int m, long long int n) {
  if (n == 0) return m;
  if (n <= M) {
    return phi[m % sz[n]][n] + (m / sz[n]) * phi[sz[n]][n];
  }
  if (m <= v[n] * v[n]) {
    return how[m] - n + 1;
  }
  if (m <= v[n] * v[n] * v[n] && m < MAX) {
    long long int sx = how[sqrt2(m)];
    long long int ans = how[m] - (sx + n - 2) * (sx - n + 1) / 2;
    for (int i = n + 1; i <= sx; ++i) {
      ans += how[m / v[i]];
    }
    return ans;
  }
  return lehmer(m, n - 1) - lehmer(m / v[n], n - 1);
}
long long int p2(long long int m, int n) {
  long long int ans = 0;
  for (long long int i = 2; i * i <= m; i++) {
    if (how[i] > n && prime[i]) ans += pi(m / i) - pi(i) + 1;
  }
  return ans;
}
long long int pi(long long int m) {
  if (m < MAX) return how[m];
  long long int y = 2;
  for (y = 1; y * y * y <= m; y++) {
  }
  long long int n = how[y];
  long long int ans = lehmer(m, n) + n - 1 - p2(m, n);
  return ans;
}
void solve() {
  long long int n, ans = 0, temp1 = 0;
  cin >> n;
  v.push_back(0);
  for (long long int i = 2; i < MAX; i++) prime[i] = 1;
  for (long long int i = 2; i < MAX; i++) {
    if (prime[i]) {
      v.push_back(i);
      if (i * i * i <= n) ans++;
      if (i * i <= n) ans--;
      for (long long int j = i * i; j < MAX; j += i) prime[j] = 0;
    }
  }
  for (long long int i = 2; i < MAX; i++) how[i] = how[i - 1] + prime[i];
  for (int i = 0; i <= MAX; i++) {
    phi[i][0] = i;
  }
  sz[0] = 1;
  for (long long int i = 1; i <= M; i++) {
    sz[i] = v[i] * sz[i - 1];
    for (long long int j = 1; j <= MAX; j++) {
      phi[j][i] = phi[j][i - 1] - phi[j / v[i]][i - 1];
    }
  }
  for (long long int i = 2; i * i <= n; i++) {
    if (prime[i]) ans += pi(n / i) - pi(i) + 1;
  }
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  srand(time(NULL));
  ;
  long long int t = 1;
  while (t--) {
    solve();
  }
}