Start 2024-05-25 14:30:00

0525小测B班

End 2024-05-25 15:20:00
Contest is over.
Now 2026-11-19 00:33:25

D. 开关灯2

Description

将n个灯泡编号为1、2、3、……、n,开始时,灯泡全不亮。 现有n个人去拉开关,第一个人把1的倍数的灯号开关都拉一下,第二个人把2的倍数的灯号都拉一下,第三个人把3的倍数的灯号都拉一下,……直到第n个人将第n号灯泡都拉一下。请问:这n个人全拉完后,有多少个灯泡是亮的?

Input

输入一个整数n(1<n\le1 000 000 000)。

Output

输出一个整数,表示有多少个灯泡是亮的。

Examples

Input

100

Output

10

Hint

因为数据规模大,朴素的模拟算法可能会超时。


Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit