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;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 50004567;
long long n;
bool c[N];
int t[N];
vector<int> p;
map<long long, long long> ans;
inline void rec0(long long i, int j) {
  if (j == 0) return;
  if (i < N) {
    ans[i * N + j] = 0;
    return;
  }
  rec0(i, j - 1);
  rec0(i / p[j - 1], j - 1);
}
int f[N / 9];
void ubd(int x) {
  ++x;
  while (x < N / 9) {
    f[x]++;
    x += (x & (-x));
  }
}
int qry(int x) {
  ++x;
  int ans = 0;
  while (x) {
    ans += f[x];
    x -= (x & (-x));
  }
  return ans;
}
inline long long rec(long long i, int j) {
  if (j == 0) return i;
  if (i < N) return ans[i * N + j];
  return rec(i, j - 1) - rec(i / p[j - 1], j - 1);
}
void solv() {
  cin >> n;
  c[0] = c[1] = true;
  int z = 0;
  int uu = sqrt(n) + 100;
  for (int i = 1; i < N; ++i) {
    if (c[i]) continue;
    t[i] = z;
    if (i * 1LL * i < N) {
      for (int j = i * i; j < N; j += i) {
        if (!c[j]) t[j] = z;
        c[j] = true;
      }
    }
    ++z;
  }
  for (int i = 1; i <= uu; ++i) {
    if (!c[i]) p.push_back(i);
  }
  long long yans = 0;
  for (int i = 0; i < p.size(); ++i) {
    if (p[i] * 1LL * p[i] * p[i] <= n)
      ++yans;
    else
      break;
  }
  for (int i = 0; i < p.size(); ++i) {
    if (p[i] * 1LL * p[i] < n) {
      if (p.back() <= n / p[i]) rec0(n / p[i], ((int)(p).size()) - 1);
    }
  }
  int u = 1;
  for (auto it = ans.begin(); it != ans.end(); ++it) {
    while (u < it->first / N) {
      ++u;
      ubd(t[u]);
    }
    ans[it->first] = u - qry(it->first % N - 1);
  }
  for (int i = 0; i < p.size(); ++i) {
    if (p[i] * 1LL * p[i] < n) {
      if (p.back() <= n / p[i])
        yans += rec(n / p[i], ((int)(p).size()) - 1) - 1 + ((int)(p).size()) -
                1 - (i + 1);
      else {
        for (int j = i + 1; j < p.size(); ++j) {
          if (p[i] * 1LL * p[j] <= n)
            ++yans;
          else
            break;
        }
      }
    }
  }
  cout << yans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0);
  int tt = 1;
  while (tt--) {
    solv();
  }
  return 0;
}