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;
using namespace std;
long long sqrt2(long long x) {
  long long r = (long long)sqrt(x - 0.1);
  while (r * r <= x) ++r;
  return r - 1;
}
long long sqrt3(long long x) {
  long long r = (long long)cbrt(x - 0.1);
  while (r * r * r <= x) ++r;
  return r - 1;
}
const int N = 1e6 + 2;
long long L[N], R[N];
long long getans(long long n) {
  long long rn = sqrt2(n);
  for (long long i = 1; i <= rn; ++i) R[i] = n / i - 1;
  long long ln = n / rn + 1;
  for (long long i = 1; i <= ln; ++i) L[i] = i - 1;
  for (long long p = 2; p <= rn; ++p) {
    if (L[p] == L[p - 1]) continue;
    for (long long i = 1, tn = min(n / (p * p), rn); i <= tn; ++i) {
      R[i] -= (i * p <= rn ? R[i * p] : L[n / (i * p)]) - L[p - 1];
    }
    for (long long i = ln; i >= p * p; --i) {
      L[i] -= L[i / p] - L[p - 1];
    }
  }
  long long ans = L[sqrt3(n)];
  for (long long p = 2; p <= rn; ++p) {
    if (L[p] == L[p - 1]) continue;
    ans += R[p] - L[p];
  }
  return ans;
}
int main() {
  long long n;
  while (cin >> n) {
    cout << getans(n) << endl;
  }
  return 0;
}