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;
inline int read() {
  char ch = getchar();
  int w = 1, c = 0;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') w = -1;
  for (; isdigit(ch); ch = getchar()) c = (c << 1) + (c << 3) + (ch ^ 48);
  return w * c;
}
const int M = 1e6 + 10;
int P[M], ct;
bool p[M];
void sieve(int n) {
  for (int i = 2; i <= n; i++) {
    if (!p[i]) P[++ct] = i;
    for (int j = 1; j <= ct && P[j] * i <= n; j++) {
      p[i * P[j]] = 1;
      if (i % P[j] == 0) break;
    }
  }
}
int id1[M], id2[M], b;
long long g[M], a[M], val[M], n;
inline int home(long long x) { return (x <= b ? id1[x] : id2[n / x]); }
int main() {
  cin >> n;
  b = sqrt(n);
  sieve(b);
  long long ans = 0;
  for (int i = (1); i <= (ct); ++i) {
    if (1ll * P[i] * P[i] * P[i] <= n) ans++;
  }
  int m = 0;
  for (long long i = 1; i <= n; i = n / a[m] + 1) {
    a[++m] = n / i;
    g[m] = a[m] - 1;
    val[m] = i;
    long long j = a[m];
    j <= b ? id1[j] = m : id2[n / j] = m;
  }
  for (int i = (1); i <= (ct); ++i) {
    long long sq = 1ll * P[i] * P[i];
    double inv = 1.0 / P[i];
    for (int j = 1; j <= m && sq <= a[j]; j++) {
      g[j] -= g[home((long long)(a[j]) * inv + 1e-9)] - i + 1;
    }
  }
  for (int i = (1); i <= (m); ++i) {
    long long num = g[i] - g[i + 1];
    if (val[i] < a[i]) {
    } else {
      ans = (ans + num * (g[home(val[i])] - g[i + 1]) - num);
    }
  }
  cout << ans << "\n";
  return 0;
}