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 long long N = 1e6 + 1;
vector<long long> p;
bool np[N];
map<long long, long long> Phi[N], f[N], PI;
void eratos() {
  for (long long i = 2; i < N; ++i)
    if (not np[i]) {
      p.push_back(i);
      for (long long j = i * i; j < N; j += i) np[j] = true;
    }
}
long long root(long long x, long long k) {
  if (k == 1) return x;
  long long be = 1, en = sqrt(x);
  while (be != en) {
    long long mi = (be + en) / 2;
    if (pow(mi + 1, k) > x)
      en = mi;
    else
      be = mi + 1;
  }
  return be;
}
long long phi(long long x, long long a) {
  if (Phi[a].count(x)) return Phi[a][x];
  if (a == 1) return (x + 1) / 2;
  long long res = phi(x, a - 1) - phi(x / p[a], a - 1);
  return Phi[a][x] = res;
}
long long pi(long long x) {
  if (x < N) return upper_bound(p.begin(), p.end(), x) - p.begin() - 1;
  if (PI.count(x)) return PI[x];
  long long a = pi(root(x, 4));
  long long b = pi(root(x, 2));
  long long c = pi(root(x, 3));
  long long res = phi(x, a) + (b + a - 2) * (b - a + 1) / 2;
  for (long long i = a + 1; i <= b; ++i) res -= pi(x / p[i]);
  for (long long i = a + 1; i <= c; ++i) {
    long long bo = pi(root(x / p[i], 2));
    for (long long j = i; j <= bo; ++j) res -= pi(x / p[i] / p[j]) - (j - 1);
  }
  return PI[x] = res;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  p.push_back(1);
  eratos();
  long long n;
  cin >> n;
  long long ans = pi(root(n, 3));
  for (long long i = 1; p[i] * p[i] < n; ++i) {
    ans += pi(n / p[i]) - i;
  }
  cout << ans << endl;
}