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>
const int lima = 201, limn = 50001, C = 10000001, D = 700001;
int i, j, pr[D], pi[C], phi[lima][limn], ipr = 1;
bool p[C];
long long a, res = 0;
long long f_phi(long long a, long long x) {
  if (x < limn && a < lima)
    return phi[a][x];
  else if (a == 1)
    return x / 2 + x % 2;
  else
    return f_phi(a - 1, x) - f_phi(a - 1, x / pr[a]);
}
long long f_pi(long long x) {
  if (x < C) return pi[x];
  long long za = floor(pow(x, 0.25)), zb = floor(pow(x, 0.5)),
            zc = floor(pow(x, 0.3333333333));
  long long a = pi[za], b = pi[zb], c = pi[zc], wynn = 0, bb, w;
  wynn = f_phi(a, x) + (b + a - 2) * (b - a + 1) / 2;
  for (long long i = a + 1; i <= b; i++) {
    w = x / pr[i];
    za = ceil(pow(w, 0.5));
    bb = pi[za];
    wynn = wynn - f_pi(w);
    if (i <= c) {
      for (long long j = i; j <= bb; j++) wynn = wynn - f_pi(w / pr[j]) + j - 1;
    }
  }
  return wynn;
}
int main() {
  for (i = 2; i * i < C; i++) {
    if (p[i] == 0) {
      if (ipr < D) pr[ipr] = i, ipr++;
      for (j = i * i; j < C; j += i) p[j] = 1;
      pi[i]++;
    }
    pi[i] += pi[i - 1];
  }
  for (; i < C; i++) {
    if (p[i] == 0) pr[ipr] = i, ipr++, pi[i]++;
    pi[i] += pi[i - 1];
  }
  for (i = 1; i < limn; i++) phi[1][i] = i % 2 + i / 2;
  for (i = 2; i < lima; i++) {
    for (j = 1; j < limn; j++) {
      phi[i][j] = phi[i - 1][j] - phi[i - 1][j / pr[i]];
    }
  }
  scanf("%I64d", &a);
  for (long long ii = 2; ii * ii <= a; ii++)
    if (p[ii] == 0) res = res + f_pi(a / ii) - pi[ii];
  for (long long ii = 2; ii * ii * ii <= a; ii++)
    if (p[ii] == 0) res++;
  printf("%I64d\n", res);
  return 0;
}