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 = 500000 + 5;
bool notPri[N];
int pre[N], pri[N];
void Init() {
  notPri[1] = 1;
  for (int i = 2; i * i < N; i++)
    if (!notPri[i])
      for (int j = i * 2; j < N; j += i) notPri[j] = 1;
  for (int i = 2; i < N; i++) {
    if (!notPri[i]) pri[++pri[0]] = i;
    pre[i] = pri[0];
  }
}
const int P = 100000 + 5, Q = 100 + 5;
int f[P][Q];
int Sqrt(long long x) { return floor(sqrt(x)); }
long long F(long long n, int p) {
  if (n < P && p < Q && f[n][p]) return f[n][p];
  long long ans = 0;
  if (p <= 0)
    ans = n - 1;
  else {
    int sqr = pre[Sqrt(n / pri[p])];
    ans = F(n, p - 1) - (F(n / pri[p], min(p - 1, sqr)) - p + 1);
  }
  if (n < P && p < Q) f[n][p] = ans;
  return ans;
}
int main() {
  Init();
  for (int i = 1; i < P; i++) F(i, pre[Sqrt(i)]);
  long long n, cnt = 0;
  cin >> n;
  for (int i = 2; 1LL * i * i * i <= n; i++)
    if (!notPri[i]) cnt++;
  for (int i = 1; i <= pri[0]; i++) {
    int j = pri[i];
    if (1LL * j * j >= n) break;
    cnt += F(n / j, pre[Sqrt(n / j)]) - i;
  }
  cout << cnt;
  return 0;
}