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;
long long dp[100][10010];
unsigned int ar[(400010 >> 6) + 5] = {0};
int len = 0, primes[40000], counter[400010];
void Sieve() {
  (((ar[(0) >> 6]) |= (1 << (((0) >> 1) & 31)))),
      (((ar[(1) >> 6]) |= (1 << (((1) >> 1) & 31))));
  for (int i = 3; (i * i) < 400010; i++, i++) {
    if (!(((ar[(i) >> 6]) & (1 << (((i) >> 1) & 31))))) {
      int k = i << 1;
      for (int j = (i * i); j < 400010; j += k)
        (((ar[(j) >> 6]) |= (1 << (((j) >> 1) & 31))));
    }
  }
  for (int i = 1; i < 400010; i++) {
    counter[i] = counter[i - 1];
    if ((((i) && ((i)&1) &&
          (!(((ar[((i)) >> 6]) & (1 << ((((i)) >> 1) & 31)))))) ||
         ((i) == 2)))
      primes[len++] = i, counter[i]++;
  }
}
void init() {
  Sieve();
  for (int n = 0; n < 100; n++) {
    for (int m = 0; m < 10010; m++) {
      if (!n)
        dp[n][m] = m;
      else
        dp[n][m] = dp[n - 1][m] - dp[n - 1][m / primes[n - 1]];
    }
  }
}
long long phi(long long m, int n) {
  if (n == 0) return m;
  if (primes[n - 1] >= m) return 1;
  if (m < 10010 && n < 100) return dp[n][m];
  return phi(m, n - 1) - phi(m / primes[n - 1], n - 1);
}
long long Lehmer(long long m) {
  if (m < 400010) return counter[m];
  long long w, res = 0;
  int i, a, s, c, x, y;
  s = sqrt(0.9 + m), y = c = cbrt(0.9 + m);
  a = counter[y], res = phi(m, a) + a - 1;
  for (i = a; primes[i] <= s; i++)
    res = res - Lehmer(m / primes[i]) + Lehmer(primes[i]) - 1;
  return res;
}
long long int arr[400000];
bitset<400000> arr2;
long long int prime() {
  long long int i, j;
  arr[0] = 2;
  arr2[1] = 1;
  arr2[0] = 1;
  for (long long int i = 4; i <= 400000; i += 2) arr2[i] = 1;
  for (i = 3; i <= sqrt(400000); i = i + 2) {
    if (arr2[i] == 0) {
      for (j = i * i; j <= 400000; j = j + i + i) {
        arr2[j] = 1;
      }
    }
  }
  j = 1;
  for (i = 3; i <= 400000; i = i + 2) {
    if (arr2[i] == 0) {
      arr[j] = i;
      j++;
    }
  }
  return (j);
}
long long int check(long long int n) {
  long long int res = 0;
  while (1) {
    if (res * res * res > n) break;
    res++;
  }
  res--;
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int k = prime();
  init();
  long long int n, res = 0;
  cin >> n;
  for (long long int i = 0; arr[i] * arr[i] <= n; i++) {
    long long int val = n / arr[i];
    val = Lehmer(val);
    if (i + 1 < val) {
      res += (val - (i + 1));
    }
  }
  long long int val = check(n), h;
  h = lower_bound(arr, arr + k, val) - arr;
  if (arr[h] <= val) h++;
  cout << res + h << endl;
  return 0;
}