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;
int a[320000], v;
long long b[320000], ans;
double inv[320000];
void prime(long long N) {
  for (int i = 1; i <= v; ++i) a[i] = i, b[i] = N / i, inv[i] = 1.0 / i;
  for (int p = 2; p <= v; ++p)
    if (a[p] != a[p - 1]) {
      int c = a[p - 1], e = min(N / p / p, (long long)v);
      for (int i = 1; i * p <= v; ++i) b[i] -= b[i * p] - c;
      double m = N / p;
      for (int i = v / p + 1; i <= e; ++i)
        b[i] -= a[(int)(m * inv[i] + 1e-8)] - c;
      if (p <= v / p)
        for (int i = v; i >= p * p; --i)
          a[i] -= a[(int)(i * inv[p] + 1e-8)] - c;
    }
}
int main() {
  long long N;
  cin >> N;
  v = sqrt(N);
  prime(N);
  ans = a[(int)(pow(N, 1.0 / 3) + 1e-8)];
  for (int p = 2; p <= v; ++p)
    if (a[p] != a[p - 1]) ans += b[p];
  cout << ans - a[v] * (a[v] + 1) / 2;
  return 0;
}