You are calibrating a hash table whose bucket count should be prime. As a first step you need to know how many candidate primes exist below a threshold. Given a non-negative integer n, count how many prime numbers are strictly less than n.
A prime is an integer greater than 1 whose only positive divisors are 1 and itself.
Input format
A single line with one non-negative integer n.
Output format
A single integer: the count of primes p with p < n.
Constraints
- 0 ≤ n ≤ 2000000