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 N = 320000, P = 100;
bool vis[N];
int predp[P][N * 2];
long long q[N];
struct hash {
  const static int mod = 1048575;
  int cnt, fir[mod + 1], nxt[N * 2], data[N * 2];
  long long key[N * 2];
  inline int ins(long long x) {
    key[++cnt] = x;
    nxt[cnt] = fir[x & mod];
    return fir[x & mod] = cnt;
  }
  inline int& operator[](long long x) {
    for (int i = fir[x & mod]; i; i = nxt[i])
      if (key[i] == x) return data[i];
    return data[ins(x)];
  }
} pre;
int dp(int i, long long j) {
  if (j < q[i + 1]) return 1;
  if (!i) return j;
  if (!j) return 0;
  if (i < P && j < N) return predp[i][j];
  if (i > pre[j]) return dp(pre[j], j) - i + pre[j];
  return dp(i - 1, j) - dp(i - 1, j / q[i]);
}
int main() {
  int r = 0, k;
  long long i, j, n, ans = 0;
  for (i = 2; i < N; ++i) {
    if (!vis[i]) q[++r] = i;
    for (j = 1; j <= r && i * q[j] < N; ++j) {
      vis[i * q[j]] = true;
      if (!(i % q[j])) break;
    }
  }
  for (j = 1; j < N; ++j) predp[0][j] = j;
  for (i = 1; i < P; ++i)
    for (j = 1; j < N; ++j)
      if (j < q[i + 1])
        predp[i][j] = 1;
      else
        predp[i][j] = predp[i - 1][j] - predp[i - 1][j / q[i]];
  cin >> n;
  for (i = 1; i <= r && q[i] * q[i] * q[i] <= n; ++i) ++ans;
  for (; r && q[r] * q[r] > n; --r)
    ;
  k = r;
  for (i = 1; i <= n; i = j + 1) {
    j = n / (n / i);
    for (; k && q[k] * q[k] > n / i; --k)
      ;
    pre[n / i] = k;
  }
  for (i = 1; i <= r; ++i) ans += r - i + dp(r, n / q[i]) - 1;
  cout << ans << endl;
  return 0;
}