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 JAVA):

Solution:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		System.out.println(f(n));
	}

	long f(long n) {
		int Len = (int) 4e5;
		long[] pi_upper = new long[Len];
		long[] pi_lower = new long[Len];
		for (int i = 1; i < Len; ++i) {
			pi_lower[i] = i;
			pi_upper[i] = n / i;
		}
		boolean[] isPrime = new boolean[Len];
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;

		ArrayList<Integer> primeList = new ArrayList<>();
		for (int i = 2; i < isPrime.length; ++i) {
			if (!isPrime[i]) {
				continue;
			}
			primeList.add(i);
			for (int j = i * 2; j < isPrime.length; j += i) {
				isPrime[j] = false;
			}
		}
		for (int t = 0; t < primeList.size(); ++t) {
			int p = primeList.get(t);
			for (int i = 1; i < Len && n / i >= (long) p * p; ++i) {
				pi_upper[i] -= ((long) p * i < Len ? pi_upper[p * i] : pi_lower[(int) (n / i / p)]) - (t + 1);
			}
			for (int i = Len - 1; i >= (long) p * p; --i) {
				pi_lower[i] -= pi_lower[i / p] - (t + 1);
			}
		}
		long ans = 0;
		for (long p : primeList) {
			if (p * p > n) {
				break;
			}
			if (p * p * p <= n && p * p * p > 0) {
				++ans;
			}
			if (n / p > p) {
				if (p < Len)
					ans += pi_upper[(int) p] - pi_lower[(int) p];
				else
					ans += pi_lower[(int) (n / p)] - pi_lower[(int) p];
			}
		}
		return ans;
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}