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 ll = long long;
using vl = vector<ll>;
unordered_map<ll, ll> cache;
ll sz;
vl pi, pl;
void ini(ll n = 30000000) {
  sz = n;
  pi.assign(n + 1, 1);
  pi[0] = pi[1] = 0;
  for (ll i = 2; i <= n; ++i)
    if (pi[i]) {
      pl.push_back(i);
      if (n / i >= i)
        for (ll j = i * i; j <= n; j += i) pi[j] = 0;
    }
  partial_sum(pi.begin(), pi.end(), pi.begin());
}
ll phi(ll x, ll a) {
  if (a == 1 || !x) return (x + 1) / 2;
  ll &r = cache[(x << 10) + a];
  if (r) return r;
  return r = phi(x, a - 1) - phi(x / pl[a - 1], a - 1);
}
ll get_pi(ll n) {
  if (n < sz) return pi[n];
  ll a = get_pi(sqrt(sqrt(n))), b = get_pi(sqrt(n));
  ll c = get_pi(cbrt(n));
  ll r = phi(n, a) + (b + a - 2) * (b - a + 1) / 2;
  for (int i = a + 1; i <= b; ++i) {
    ll w = n / pl[i - 1];
    r -= get_pi(w);
    if (i <= c) {
      int upp = get_pi(sqrt(w));
      for (int j = i; j <= upp; ++j) r += j - 1 - get_pi(w / pl[j - 1]);
    }
  }
  return r;
}
int main() {
  ios ::sync_with_stdio(0);
  ll n;
  cin >> n;
  ini();
  ll ans = 0;
  for (ll i : pl)
    if (i * i * i <= n)
      ans++;
    else
      break;
  for (ll i : pl)
    if (i * i <= n) ans += get_pi(n / i) - get_pi(i);
  cout << ans << '\n';
}