A number is called almost prime if it has exactly two distinct prime divisors. For example, numbers 6, 18, 24 are almost prime, while 4, 8, 9, 42 are not. Find the amount of almost prime numbers which are between 1 and n, inclusive.

Input

Input contains one integer number n (1 ≤ n ≤ 3000).

Output

Output the amount of almost prime numbers between 1 and n, inclusive.

Examples

Input

10


Output

2


Input

21


Output

8
# https://codeforces.com/contest/26/problem/A

"""
Find the number of almost primes between 1 and n.
A number is almost prime if it has exactly two prime divisors.

Find the number of primes between 1 and n. Then find the number of combinations with product less than 1.
(These are all distinct because of uniqueness of prime factorisation)
"""

from math import floor, log
from itertools import combinations


def sieve(n):
    """Returns all primes in the range [0, n]"""

    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    # Can have no prime numbers greater than sqrt n
    for i in range(2, floor(n ** 0.5) + 1):
        if is_prime[i]:
            # Eliminate proper multiples of i
            for j in range(2, n // i + 1):
                is_prime[i * j] = False

    primes = [i for i in range(n + 1) if is_prime[i]]

    return primes


def main():
    n = int(input())
    count = 0
    for a, b in combinations(sieve(n), 2):
        # We want a**x b <= n
        base = 1
        while base <= n:
            base *= a
            candidate = base * b
            # We want a**x b**y <= n
            while candidate <= n:
                count += 1
                candidate *= b

    return count


if __name__ == '__main__':
    print(main())
