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 long long N = 5e6 + 10;
const long long PN = 2e4 + 10, PK = 55;
long long f[PN][PK];
long long pri[N], len, vi[N], s[N];
void pre() {
  long long n = N - 10;
  for (register long long i = (2); i <= (n); ++i) {
    if (!vi[i]) {
      vi[i] = i;
      pri[++len] = i;
    }
    for (register long long j = (1); j <= (len); ++j) {
      if (pri[j] * i > n || vi[i] < pri[j]) break;
      vi[pri[j] * i] = pri[j];
    }
  }
  vi[1] = 1;
  for (register long long i = (1); i <= (n); ++i)
    s[i] = s[i - 1] + (vi[i] == i);
  for (register long long i = (1); i <= (PN - 10); ++i) {
    f[i][0] = i;
    for (register long long j = (1); j <= (PK - 5); ++j)
      f[i][j] = f[i][j - 1] - f[i / pri[j]][j - 1];
  }
}
long long dp(long long x, long long y) {
  if (x <= PN - 10 && y <= PK - 5) return f[x][y];
  if (!x || !y) return x;
  if (1ll * pri[y] * pri[y] >= x && x < N - 10) return max(0ll, s[x] - y);
  return dp(x, y - 1) - dp(x / pri[y], y - 1);
}
long long work(long long m) {
  if (m < N - 10) return s[m] - 1;
  long long y = (long long)cbrt(m * 1.0), n = s[y];
  long long sum = dp(m, n) + n - 1;
  for (n++; 1ll * pri[n] * pri[n] <= m; n++)
    sum -= (work(m / pri[n]) - work(pri[n] - 1));
  return sum;
}
signed main() {
  long long m;
  pre();
  scanf("%lld", &m);
  long long y = (long long)cbrt(1.0 * m);
  long long sum = s[y] - 1;
  for (register long long i = (1); i <= (len); ++i) {
    if (1ll * pri[i] * pri[i] > m) break;
    sum += (work(m / pri[i]) - work(pri[i]));
  }
  printf("%lld\n", sum);
  return 0;
}