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 is[350000];
int prime[100000], cnt, num_state, m;
long long xp;
bool us[350000];
long long ans;
map<long long, int> hs;
long long s_cnt[320000];
long long l_cnt[320000];
int used[320000];
void init(int n, int x) {
  int i, j, s, p, q;
  cnt = 0;
  for (i = 0; i <= n; i++) is[i] = false;
  for (i = 2; i <= n; i++) {
    if (!is[i]) {
      if (i >= x) prime[cnt++] = i;
      if (i <= 1e3) {
        j = i * i;
        while (j <= n) {
          is[j] = true;
          j += i;
        }
      }
    }
  }
}
int lower_bound(int left, int right, long long x) {
  int mid;
  while (left <= right) {
    mid = (left + right) >> 1;
    if (prime[mid] <= x)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return right;
}
void dfs(int fk, int flag, int id, long long n, long long &res, int rd) {
  int i, j, s, p, q, ip1, ip2;
  num_state++;
  if (fk == 0)
    res += flag * (n - 1);
  else
    res += flag * n;
  for (i = id + 1; i < rd && (long long)prime[i] * (long long)prime[i] <= n;
       i++)
    dfs(fk + 1, -flag, i, n / prime[i], res, rd);
  j = i;
  for (; i < rd && i - j < n / prime[i] && prime[i] <= n; i++)
    res += -flag * n / prime[i];
  if (i >= rd || prime[i] > n) return;
  ip1 = ip2 = lower_bound(i, rd - 1, n);
  for (s = 1; s <= n / prime[i]; s++) {
    while (ip2 >= i && prime[ip2] > n / s) ip2--;
    while (ip1 >= i && prime[ip1] > n / (s + 1)) ip1--;
    res += -flag * (long long)(ip2 - ip1) * (long long)s;
  }
}
long long solve(long long n) {
  int v = (int)sqrt(n);
  long long ret = 0;
  for (int i = 2; i <= v; ++i) s_cnt[i] = i - 1;
  for (int i = 1; i <= v; ++i) l_cnt[i] = n / i - 1;
  fill(used, used + v + 1, 0);
  for (int i = 2; i <= v; ++i) {
    if (s_cnt[i] == s_cnt[i - 1]) continue;
    const int p = i;
    int p_cnt = s_cnt[p - 1];
    const long long q = (long long)p * (long long)p;
    l_cnt[1] -= l_cnt[p] - p_cnt;
    int interval = (p & 1) + 1;
    long long end = min((long long)v, n / q);
    for (int i = p + interval; i <= end; i += interval) {
      if (used[i]) continue;
      long long d = (long long)i * (long long)p;
      if (d <= v) {
        l_cnt[i] -= l_cnt[d] - p_cnt;
      } else {
        int t = (int)(n / d);
        l_cnt[i] -= s_cnt[t] - p_cnt;
      }
    }
    if (q <= v)
      for (int i = q; i <= end; i += p * interval) used[i] = 1;
    for (int i = v; i > q - 1; --i) {
      int t = i / p;
      s_cnt[i] -= s_cnt[t] - p_cnt;
    }
  }
  return l_cnt[1];
}
int main() {
  int j, i;
  long long n;
  num_state = 0;
  memset(us, false, sizeof(us));
  cin >> n;
  for (m = 1; (long long)m * (long long)m * (long long)m <= n; m++)
    ;
  m--;
  init(m, 2);
  ans = cnt;
  hs.clear();
  for (j = 2; (long long)j * (long long)j <= n; j++) {
    if (us[j]) continue;
    xp = n / j;
    for (m = 1; (long long)m * (long long)m <= xp; m++)
      ;
    m--;
    init(m, 2);
    ans += solve(xp) - solve(j);
    for (i = j * 2; i <= 320000; i += j) us[i] = true;
  }
  cout << ans << endl;
  return 0;
}