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 MAXPRIME = 1000000;
const int MAXPRIMECNT = 78498;
int minPrimeFactor[MAXPRIME];
int nPrime, prime[MAXPRIMECNT];
long long prime2[MAXPRIMECNT];
int primePi[MAXPRIME];
bool isPrime(int n) { return minPrimeFactor[n] == n; }
void initPrime() {
  for (int i = 2; i < MAXPRIME; i++) {
    if (!minPrimeFactor[i]) minPrimeFactor[i] = prime[nPrime++] = i;
    if (i >= MAXPRIME / i) continue;
    for (int j = i * i; j < MAXPRIME; j += i)
      if (!minPrimeFactor[j]) minPrimeFactor[j] = i;
  }
  for (int i = (0); i < (nPrime); i++) {
    primePi[prime[i]] = 1;
    prime2[i] = (long long)prime[i] * prime[i];
  }
  for (int i = (1); i < (MAXPRIME); i++) primePi[i] += primePi[i - 1];
}
const int BOUND = 100000;
const int MAXSTORE = 5000000;
int startIdx[BOUND], bound[BOUND];
long long phi[MAXSTORE];
long long calc(long long n, int m) {
  if (m < 0) return n;
  int mm = m;
  if (prime2[m] > n) mm = upper_bound(prime2, prime2 + m, n) - prime2 - 1;
  long long res;
  if (mm < 0) {
    res = n;
  } else if (n < BOUND) {
    res = phi[startIdx[n] + mm];
  } else {
    res = calc(n, mm - 1) - calc(n / prime[mm], mm - 1);
  }
  return res + mm - m;
}
void initPhi() {
  startIdx[1] = 0;
  bound[1] = 0;
  for (int i = (2); i < (BOUND); i++) {
    bound[i] = upper_bound(prime2, prime2 + nPrime, i) - prime2;
    startIdx[i] = startIdx[i - 1] + bound[i - 1];
  }
  int idx = -1;
  for (int n = (1); n < (BOUND); n++) {
    for (int m = (0); m < (bound[n]); m++) {
      phi[++idx] = calc(n, m - 1) - calc(n / prime[m], m - 1);
    }
  }
}
long long calcPrimePi(long long n) {
  if (n < 10) return primePi[n];
  int m = upper_bound(prime2, prime2 + nPrime, n) - prime2 - 1;
  return calc(n, m) + m;
}
long long n;
int main() {
  ios_base::sync_with_stdio(false);
  initPrime();
  initPhi();
  cin >> n;
  long long res = 0;
  for (int i = 0; prime2[i] <= n / prime[i]; i++, res++) {
  }
  for (int i = 0; prime[i] <= n / prime[i]; i++) {
    res += calcPrimePi(n / prime[i]) - i - 1;
  }
  cout << res << endl;
  return 0;
}