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;
bool c[10000010];
int prime[10000010];
int tot;
void Euler(int n) {
  tot = 0;
  for (int i = 2; i <= n; i++) {
    if (!c[i]) prime[tot++] = i;
    for (int j = 0; j < tot; j++) {
      if (i * prime[j] > n) break;
      c[i * prime[j]] = true;
      if (i % prime[j] == 0) break;
    }
  }
}
int pi[10000010];
const int Maxm = 100010;
const int Maxd = 6;
const int num = 310;
int f[num][Maxm + 1];
int pre[Maxd + 1];
void init() {
  Euler(10000010 - 1);
  for (int i = 2; i < 10000010; i++) {
    pi[i] = pi[i - 1];
    if (!c[i]) pi[i]++;
  }
  pre[0] = 1;
  for (int i = 1; i <= Maxd; i++) pre[i] = pre[i - 1] * prime[i - 1];
  for (int i = 0; i < num; i++)
    for (int j = 0; j <= Maxm; j++)
      if (!i)
        f[i][j] = j;
      else
        f[i][j] = f[i - 1][j] - f[i - 1][j / prime[i - 1]];
}
long long phi(int n, long long m) {
  if (!n) return m;
  if (n <= Maxd) return f[n][m % pre[n]] + (m / pre[n]) * f[n][pre[n]];
  if (m <= prime[n - 1]) return 1;
  if (m <= prime[n - 1] * prime[n - 1] && m < 10000010) return pi[m] - n + 1;
  if (m <= Maxm && n < num) return f[n][m];
  return phi(n - 1, m) - phi(n - 1, m / prime[n - 1]);
}
long long lehmer(long long m) {
  if (m < 10000010) return pi[m];
  int q2 = sqrt(m + 0.5), q3 = cbrt(m + 0.5);
  int n = pi[q3];
  long long res = phi(n, m) + n - 1;
  for (int i = n; prime[i] <= q2; i++)
    res = res - lehmer(m / prime[i]) + lehmer(prime[i]) - 1;
  return res;
}
int main() {
  init();
  long long n;
  cin >> n;
  long long ans = 0;
  for (int i = 0; (long long)prime[i] * prime[i] * prime[i] <= n; i++) ans++;
  for (int i = 0; (long long)prime[i] * prime[i] <= n; i++)
    ans += lehmer(n / prime[i]) - pi[prime[i]];
  cout << ans << endl;
  return 0;
}