You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

求 $1,2,\cdots,N$ 中素数的个数。

Format

Input

一行一个整数 $N$。

Output

一行一个整数，表示素数的个数。

Samples

10

4

Limitation

$1 \le N \le 10^8$ 警告：请使用线性筛解决问题。