给定一个正整数$N$，询问$1$到$N$中有多少个素数。

输入格式

一个正整数$N$。

输出格式

一个数$Ans$，表示$1$到$N$中有多少个素数。

样例

样例输入

10

样例输出

4

数据范围与提示

• 30% $N \leq 100$
• 70% $N \leq 5000$
• 100% $N \leq 10000000$
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$65536\mathrm{KB}$