该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

星际航道将空间站按数字编号排列，出发点为 1 号空间站，目的地是 n 号宝藏空间站。航行会途经 1 至 n 全部空间站，编号为质数的空间站有星际陨石拦截，每一处拦截需要一枚护盾能量。

求一共需要多少枚护盾能量。

Format

Input

第一行输入一个正整数 $n(1 \leq n \leq 10^5)$, 代表宝藏位置。

Output

输出一个整数代表需要护盾的数量。

Samples

100

25

Limitation

1s, 1024KiB for each test case.