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 T1, typename T2>
inline T1 max(T1 a, T2 b) {
  return a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
  return a < b ? a : b;
}
const char lf = '\n';
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline long long ty() {
  long long a = 0;
  int b = 1, c = fetch();
  while (!isdigit(c)) b ^= c == '-', c = fetch();
  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
  return b ? a : -a;
}
}  // namespace ae86
using ae86::ty;
const int _ = 500007;
long long n, sqn, cbn, f[_] = {0}, g[_] = {0};
int main() {
  ios::sync_with_stdio(0), cout.tie(nullptr);
  n = ty(), sqn = round(sqrt(n) + 1), cbn = floor(cbrt(n) + 1e-9);
  for (int i = 1; i < sqn; i++) f[i] = n / i - 1;
  for (int i = 1; i <= sqn; i++) g[i] = i - 1;
  for (int i = 2; i <= sqn; i++) {
    if (g[i] == g[i - 1]) continue;
    for (int j = 1; j <= min(sqn - 1, n / i / i); j++) {
      if (1ll * i * j < sqn)
        f[j] -= f[i * j] - g[i - 1];
      else
        f[j] -= g[n / i / j] - g[i - 1];
    }
    for (int j = sqn; j >= 1ll * i * i; j--) g[j] -= g[j / i] - g[i - 1];
  }
  long long ans = g[cbn];
  for (int i = 2; i < sqn; i++)
    if (g[i] != g[i - 1]) ans += f[i] - g[i];
  cout << ans << lf;
  return 0;
}