No testdata at current.

题目背景

土拨鼠潘某最近学习了素数，他想知道1~n中素数有多少个

取值范围

1<=n<=1e12+10

Format

Input

输入一个n,表示上限数字为n .

Output

输出一个数，表示1~n中所有素数的数量

Samples

123 500

623

Limitation

6s, 1024KiB for each test case.