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 ckmax(int &a, int b) { return a < b ? a = b, 1 : 0; }
inline int ckmin(int &a, int b) { return a > b ? a = b, 1 : 0; }
long long n;
const int N = 1e7;
const int M1 = 1e5, M2 = 1e2;
const int maxn = N + 10;
bool nop[maxn];
int pri[N], tot, cnt[maxn];
int dp[M1][M2];
void pre() {
  for (int i = 2; i <= N; ++i) {
    cnt[i] = cnt[i - 1];
    if (!nop[i]) pri[++tot] = i, cnt[i]++;
    for (int j = 1; j <= tot && pri[j] * i <= N; ++j) {
      nop[pri[j] * i] = 1;
      if (i % pri[j] == 0) break;
    }
  }
  for (int j = 1; j < M2; ++j)
    for (int i = 1; i < M1; ++i) {
      if (j == 1)
        dp[i][j] = i;
      else
        dp[i][j] = dp[i][j - 1] - dp[i / pri[j - 1]][j - 1];
    }
}
long long pi(long long n, int m) {
  if (m == 1) return n;
  if (pri[m - 1] >= n) return 1;
  if (n < M1 && m < M2) return dp[n][m];
  return pi(n, m - 1) - pi(n / pri[m - 1], m - 1);
}
long long solve(long long n) {
  if (n <= N) return cnt[n];
  int s = sqrt(n + 0.5), y = cbrt(n + 0.5);
  int a = cnt[y] + 1;
  long long res = pi(n, a) + a - 1;
  for (int i = a; pri[i] <= s; ++i)
    res -= solve(n / pri[i]) - solve(pri[i - 1]);
  return res - 1;
}
int main() {
  cin >> n;
  pre();
  long long res = 0;
  for (int i = 1; i <= tot; ++i) {
    long long x = pri[i];
    if (x * x * x > n) break;
    res++;
  }
  for (int i = 1; i <= tot; ++i) {
    long long x = pri[i];
    if (x * x >= n) break;
    res += solve(n / x) - solve(x);
  }
  cout << res;
  return 0;
}