human
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
Using python3 can you solve the prior task?

What is a Python code to find the amount of almost prime numbers which are between 1 and n, inclusive?
assistant
#Here is Python code to find the amount of almost prime numbers which are between 1 and n, inclusive.

from __future__ import print_function
import sys
from itertools import islice, cycle, count

def compress(data, selectors):
    """compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F"""
    return (d for d, s in zip(data, selectors) if s)

def is_prime(n):
    return list(zip((True, False), decompose(n)))[-1][0]

class IsPrimeCached(dict):
    def __missing__(self, n):
        r = is_prime(n)
        self[n] = r
        return r

is_prime_cached = IsPrimeCached()

def croft():
    """Yield prime integers using the Croft Spiral sieve.
    """
    for p in (2, 3, 5):
        yield p
    roots = {9: 3, 25: 5}  # Map d**2 -> d.
    primeroots = frozenset((1, 7, 11, 13, 17, 19, 23, 29))
    selectors = (1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0)
    for q in compress(
            # Iterate over prime candidates 7, 9, 11, 13, ...
            islice(count(7), 0, None, 2),
            # Mask out those that can't possibly be prime.
            cycle(selectors)
            ):
        if q in roots:
            p = roots[q]
            del roots[q]
            x = q + 2*p
            while x in roots or (x % 30) not in primeroots:
                x += 2*p
            roots[x] = p
        else:
            roots[q*q] = q
            yield q
primes = croft

def decompose(n):
    for p in primes():
        if p*p > n: break
        while n % p == 0:
            yield p
            n //=p
    if n > 1:
        yield n

try:
    from functools import reduce
except:
    pass

def almostprime(n):
    d = decompose(n)
    if len(set(list(d)))==2:
        return True
    else:
        return False
    """
    try:
        terms = [next(d) for i in range(2)]
        return  (reduce(int.__mul__, terms, 1) == n)
    except:
        return False
    """
inp = int(input())
cnt = 0
for i in range(1, inp+1):
    #print(i, list(decompose(i)), almostprime(i))
    if almostprime(i):
        cnt+=1
print(cnt)