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 int maxn = 320000;
const double eps = 1e-9;
long long H[maxn], L[maxn];
long long f(long long n) {
  long long m, ans = 0;
  for (m = 1; m * m <= n; m++) H[m] = n / m - 1;
  for (long long i = 1; i <= m; i++) L[i] = i - 1;
  for (long long p = 2; p <= m; p++) {
    if (L[p] == L[p - 1]) continue;
    long long s = n / (p * p);
    if (s >= m) s = m - 1;
    for (long long x = 1; x <= s; x++) {
      H[x] -= (((x * p <= (m - 1)) ? H[x * p] : L[n / (x * p)]) - L[p - 1]);
    }
    for (long long x = m; x >= p * p; x--) {
      L[x] -= (L[x / p] - L[p - 1]);
    }
  }
  for (int p = 2; p < m; p++) {
    if (L[p] == L[p - 1]) continue;
    ans += H[p] - L[p];
  }
  return ans;
}
int main() {
  long long n, k;
  cin >> n;
  k = pow(n, (long double)1.0 / 3) + eps;
  long long ans = f(n) + L[k];
  cout << ans << endl;
  return 0;
}