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 maxn = 2e7;
bool A[maxn];
int primepi[maxn];
vector<long long> primes;
void pre() {
  memset(A, 0, sizeof A);
  for (int i = 2; i * i < maxn; i++)
    if (!A[i])
      for (int j = i * i; j < maxn; j += i) A[j] = 1;
  primepi[1] = 0;
  for (int i = 2; i < maxn; i++) {
    primepi[i] = primepi[i - 1];
    if (!A[i]) {
      primepi[i]++;
      primes.push_back((long long)i);
    }
  }
}
map<long long, long long> myp;
long long ppi(long long n) {
  if (n < maxn) return primepi[n];
  if (myp[n] != 0) return myp[n];
  vector<long long> sm, la;
  long long N = n;
  long long v = (long long)sqrt(n);
  for (long long i = 0; i <= v; i++) {
    sm.push_back(i - 1);
    if (i == 0)
      la.push_back(0);
    else
      la.push_back(n / i - 1);
  }
  for (long long p = 2; p <= v; p++) {
    if (sm[p - 1] == sm[p]) continue;
    long long p_cnt = sm[p - 1];
    long long q = p * 1ll * p;
    long long en = min(v, n / q);
    for (int i = 1; i <= en; i++) {
      long long d = p * 1ll * i;
      if (d <= v) {
        la[i] -= la[d] - p_cnt;
      } else {
        la[i] -= sm[n / d] - p_cnt;
      }
    }
    for (int i = v; i >= q; i--) {
      sm[i] -= sm[i / p] - p_cnt;
    }
  }
  for (int i = 1; i < la.size(); i++) myp[n / i] = la[i];
  return la[1];
}
int main() {
  pre();
  long long n;
  cin >> n;
  long long x = max(0LL, (long long)pow(n, 1. / 3) - 100);
  while (x * x * x <= n) x++;
  x--;
  long long ret = ppi(x);
  for (int i = 0; primes[i] * primes[i + 1] <= n; i++) {
    ret += max(0LL, ppi(n / primes[i]) - (i + 1));
  }
  cout << ret << endl;
}