8.2 Two Prime

Score: 30pts

Time Limit: 2.00 sec

Raju is a mathematician and has nothing to do on a Sunday. He has done a lot of research about prime numbers. So he decides to check if a number is Two-prime. A number is Two-prime if it has exactly two distinct prime divisors.

You are given an integer \(n\). You have to find the total number of Two-prime numbers in the range \(1\) to \(n\), \(1\) and \(n\) inclusive.

You are given an integer \(n\). You have to find the total number of Two-prime numbers in the range \(1\) to \(n\), \(1\) and \(n\) inclusive.

Constraints

\(1 \leq n \leq 3000\)

Input Format

The test case contains a single integer \(n\).

Output Format

You have to output a single integer on a new line, the number of Two-prime numbers in the range \(1\) to \(n\).

Example 1

Input:

10

Output:

2

Explanation:

There exist two numbers between 1 to 10 that are Two-prime. These numbers are 6 (prime divisors 2 and 3) and 10 (prime divisors 2 and 5).

10

Output:

2

Explanation:

There exist two numbers between 1 to 10 that are Two-prime. These numbers are 6 (prime divisors 2 and 3) and 10 (prime divisors 2 and 5).