Count Primes Up to N

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Count prime integers in the inclusive range [1,n]; 1 is not prime.

Input

One integer n.

Output

Number of primes in [1,n].

Subtasks

• Subtask 1 (20%): 1 ≤ n ≤ 100.

• Subtask 2 (30%): 1 ≤ n ≤ 1000.

• Subtask 3 (50%): 1 ≤ n ≤ 10000.

Examples

Example 1

Input:

10

Output:

4

Explanation: The primes at most ten are 2, 3, 5, and 7.

Example 2

Input:

1

Output:

0

Explanation: One is not prime.