Background

Description

有n个人，编号从1~n（n<=100000000，1亿），开始时，所有人都站着，接着第2个人与2的倍数位置的人坐下，然后第三个人与3的倍数位置的人按相反的操作(坐着的人站起，站着的人坐下)，以此类推，一直操作到第k（n-10<=k<=n）人，计算出站着的人的总数并打印（不需要打印站着的位置）。

注：特别强调n-10<=k<=n，即k最多小于n只有10。性能允许10s完成。

Format

Input

Output

Samples

1000
990

41

100000000
99999990

10008

Limitation

10s, 1024KiB for each test case.