[AdditionalFile4254.zip](file://AdditionalFile4254.zip?type=additional_file)

#4254. 「NordicOI 2017」Yule Lads

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 NordicOI 2017 T2 「Yule Lads」

冰岛的孩子们非常幸运，他们不仅有一个圣诞老人，还有 $N$ 个！这些圣诞小矮人被称为 Yule Lads，在圣诞节前的 $N$ 个夜晚里，每晚都会有一个小矮人来到镇上，给那些乖孩子送小礼物，给那些淘气的孩子送土豆。

在冰岛的一个小镇上，有一条街道上有 $N$ 座房子，按顺序编号为 $1$ 到 $N$。每座房子都装饰着美丽的圣诞灯，起初所有灯都是亮着的。

在圣诞节前的每个夜晚，都会有一个 Yule Lad 访问这条街道。距离圣诞节还有 $K$ 个夜晚时来访的小矮人非常喜欢数字 $K$，他只会访问那些房子编号能被 $K$ 整除的房子。此外，这些小矮人都是捣蛋鬼，他们会切换每个访问的房子的圣诞灯状态（即如果灯是亮的就关掉，如果是关的就打开）。

然而，有些小矮人感觉不舒服，没有来镇上。圣诞节当天，除了第一座房子外，所有房子的灯都是亮着的。请问有多少个小矮人来过镇上？

输入格式

输入的第一行包含一个正整数 $N$，表示 Yule Lads 的数量和街道上的房子数量。

输出格式

输出一个整数，表示来过镇上的 Yule Lads 的数量。你可以假设只有一种情况会导致所有房子的灯都亮着，除了第一座房子。

样例 1

输入

6

输出

5

考虑 $N = 6$ 的情况。有六个 Yule Lads 和六座房子。假设没有小矮人生病，以下是圣诞节前六个夜晚发生的事情：

• 圣诞节前六个夜晚，小矮人会把第 $6$ 号房子的灯关掉。
• 圣诞节前五个夜晚，小矮人会把第 $5$ 号房子的灯关掉。
• 圣诞节前四个夜晚，小矮人会把第 $4$ 号房子的灯关掉。
• 圣诞节前三个夜晚，小矮人会把第 $3$ 号房子的灯关掉，并把第 $6$ 号房子的灯打开。
• 圣诞节前两个夜晚，小矮人会把第 $2$ 号和第 $6$ 号房子的灯关掉，并把第 $4$ 号房子的灯打开。
• 圣诞节前一个夜晚，小矮人会把第 $1$ 号和第 $4$ 号房子的灯关掉，并把第 $2,3,5,6$ 号房子的灯打开。

然而，圣诞节当天，第 $4$ 号房子的灯是关着的，这与实际情况不符。

另一方面，如果只有圣诞节前四天应该来镇上的小矮人生病了，那么圣诞节当天，除了第 $1$ 号房子外，所有房子的灯都会亮着。因此，正确答案是 $5$：小矮人分别在圣诞节前 $6, 5, 3, 2, 1$ 天来过镇上。

样例 2

输入

13

输出

9

样例 3

输入

68

输出

42

数据范围与提示

详细子任务附加限制及分值如下表所示。