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 N = 1000005;
const long long M = 1000000007;
bool np[N];
int p[N], pp = 0;
void eratos() {
  np[0] = np[1] = true;
  for (int i = 2; i * i < N; i++)
    if (!np[i])
      for (int j = i * i; j < N; j += i) np[j] = true;
  for (int i = 2; i < N; i++)
    if (!np[i]) p[++pp] = i;
}
long long power(long long a, long long k) {
  long long P = 1;
  while (k) {
    if (k & 1) P = P * a;
    k /= 2;
    a = a * a;
  }
  return P;
}
long long power(long long a, long long k, long long M) {
  long long P = 1;
  for (a = a % M; k; k /= 2) {
    if (k & 1) P = P * a % M;
    a = a * a % M;
  }
  return P;
}
long long root(long long n, long long k) {
  long long x = pow(n, 1.0 / k);
  while (power(x, k) % M == power(x, k, M) && power(x, k) < n) x++;
  while (power(x, k) % M != power(x, k, M) || power(x, k) > n) x--;
  return x;
}
map<long long, long long> Phi[N];
map<long long, long long> ff;
long long phi(long long x, int a) {
  if (Phi[a].count(x)) return Phi[a][x];
  if (a == 1) return (x + 1) / 2;
  long long Result = phi(x, a - 1) - phi(x / p[a], a - 1);
  return Phi[a][x] = Result;
}
long long pi(long long x) {
  if (x < N) return upper_bound(p + 1, p + pp + 1, x) - (p + 1);
  if (ff.find(x) != ff.end()) return ff[x];
  long long a = pi(root(x, 4));
  long long b = pi(root(x, 2));
  long long c = pi(root(x, 3));
  long long Sum = phi(x, a) + (b + a - 2) * (b - a + 1) / 2;
  for (int i = a + 1; i <= b; i++) Sum -= pi(x / p[i]);
  for (int i = a + 1; i <= c; i++) {
    long long bi = pi(root(x / p[i], 2));
    for (int j = i; j <= bi; j++) Sum -= pi(x / p[i] / p[j]) - (j - 1);
  }
  return ff[x] = Sum;
}
int main() {
  eratos();
  long long n;
  cin >> n;
  long long ans = 0;
  for (int i = 1; i <= pp && p[i] * 1ll * p[i] * p[i] <= n; ++i) ++ans;
  for (int i = 1; i <= pp && p[i] * 1ll * p[i] <= n; ++i) {
    ans += pi(n / p[i]) - pi(p[i]);
  }
  cout << ans << endl;
}