Count the Number of Primes

Given a positive integer N, count the number of prime numbers in the set ({1,2,\cdots,N}). A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

For example, if N = 10, the prime numbers are 2, 3, 5, and 7, so the answer is 4.

inputFormat

The input consists of a single integer N (1 (\leq) N (\leq) 10^6).

outputFormat

Output a single integer representing the number of prime numbers among ({1,2,\cdots,N}).

sample

10

4