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;
vector<pair<long long, int> > H[1000007];
long long n, val[1000005], ans, cnt[1000005];
int S[1000005];
int m, up[1000005], p[1000005], len, b[1000005], mp[1000005];
void prepare() {
  int i, j;
  b[1] = 1;
  for (i = 2; i < 1000005; i++) {
    if (!b[i]) p[++len] = i;
    for (j = 1; j <= len; j++) {
      if (1LL * i * p[j] >= 1000005) break;
      b[1LL * i * p[j]] = 1;
      if (i % p[j] == 0) break;
    }
  }
  for (i = 1; i < 1000005; i++) S[i] = S[i - 1] + (!b[i]);
  for (i = 1; i <= len; i++) mp[p[i]] = i;
  for (i = 1000005 - 1; i >= 1; i--) mp[i] = mp[i] ? mp[i] : mp[i + 1];
}
int SQRT(long long n) {
  int p = (int)(sqrt(n));
  while (1LL * p * p <= n) p++;
  return p;
}
long long find(long long x, int t) {
  int i, u = x % 1000007, p;
  for (i = 0; i < H[u].size(); i++)
    if (H[u][i].first == x) break;
  p = H[u][i].second;
  return t > up[p] ? cnt[p] + up[p] - t : cnt[p];
}
long long Pi(int t) { return cnt[t] + up[t] - 1; }
void update(int t) {
  long long i, x = val[t], l = n / (x + 1) + 1, r = n / x;
  r = min(r, (long long)(sqrt(n)));
  for (i = l; i <= r; i++)
    if (!b[i]) ans += Pi(t) - S[i];
}
int main() {
  long long i, j = 1, q = 1;
  long long x = 0;
  cin >> n;
  prepare(), m = 1;
  for (i = 1; 1LL * p[i] * p[i] * p[i] <= n; i++) ans++;
  for (i = 1; i <= n; i = n / (val[m++]) + 1) val[m] = n / i;
  m--, sort(val + 1, val + m + 1);
  for (i = 1; i <= m; i++)
    H[val[i] % 1000007].push_back(pair<long long, int>(val[i], i));
  for (i = 1; i <= m; i++) up[i] = mp[SQRT(val[i])];
  for (i = 1; i <= up[m]; i++) {
    for (j = m; j >= q; j--) {
      if (i != 1) {
        x = find(val[j] / p[i - 1], i - 1);
        cnt[j] = cnt[j] - x - 1;
      } else
        cnt[j] = val[j] - 1;
    }
    while (q <= m && i == up[q]) update(q++);
  }
  cout << ans;
  return 0;
}