Count the primes up to N

Problem

A catalogue needs a prime-numbered code for each item. Print how many prime numbers there are from 1 to N.

Example

Input

Output

The primes are 2, 3, 5 and 7.

Try the problem first. Open one hint at a time.

Hint 1

Testing every number separately is too slow. Mark the multiples of each prime instead.

Hint 2

Start crossing out at p * p and stop the outer loop at the square root of N.

Write your Python code, run it on the examples and submit it to hidden tests.