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;
namespace SHENZHEBEI {
static const int GYN = 2333333;
char SZB[GYN], *S = SZB, *T = SZB;
inline char gc() {
  if (S == T) {
    T = (S = SZB) + fread(SZB, 1, GYN, stdin);
    if (S == T) return '\n';
  }
  return *S++;
}
inline long long read() {
  long long x = 0, f = 1;
  char ch = gc();
  for (; !isdigit(ch); ch = gc())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = gc()) x = x * 10 - 48 + ch;
  return x * f;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline char readchar() {
  char ch = gc();
  for (; isspace(ch); ch = gc())
    ;
  return ch;
}
inline long long readstr(char *s) {
  char ch = gc();
  int cur = 0;
  for (; isspace(ch); ch = gc())
    ;
  for (; !isspace(ch); ch = gc()) s[cur++] = ch;
  s[cur] = '\0';
  return cur;
}
void Print(long long *a, int s, int t) {
  for (long long i = (s); i <= int(t); ++i) printf("%lld ", a[i]);
}
void Print(int *a, int s, int t) {
  for (long long i = (s); i <= int(t); ++i) printf("%d ", a[i]);
}
void Print(char *a, int s, int t) {
  for (long long i = (s); i <= int(t); ++i) putchar(a[i]);
}
void writeln(long long x) {
  write(x);
  puts("");
}
}  // namespace SHENZHEBEI
using namespace SHENZHEBEI;
const long long N = 1000100;
long long pri[N], w[N], c[N], n, lim, m, cnt, ans;
int main() {
  n = read();
  lim = sqrt(n);
  for (long long i = 1; i <= n; i = w[m] + 1)
    w[++m] = n / (n / i), c[m] = w[m] - 1;
  for (long long i = (2); i <= int(lim); ++i)
    if (c[i] ^ c[i - 1]) {
      pri[++cnt] = i;
      for (long long j = m; w[j] >= i * i; --j)
        c[j] -= c[((w[j] / i) <= lim ? (w[j] / i) : (m - n / (w[j] / i) + 1))] -
                c[i - 1];
    }
  for (long long i = 1; i <= cnt && pri[i] * pri[i] * pri[i] <= n; ++i) ++ans;
  for (long long i = (1); i <= int(cnt); ++i)
    ans +=
        c[((n / pri[i]) <= lim ? (n / pri[i]) : (m - n / (n / pri[i]) + 1))] -
        c[((pri[i]) <= lim ? (pri[i]) : (m - n / (pri[i]) + 1))];
  writeln(ans);
}