题目描述
冰岛的孩子们非常幸运。他们有 $N$ 个圣诞老人!这些圣诞老人被称为尤拉兄弟(Yule Lads)。在圣诞节前的 $N$ 个晚上,他们中的一个会来到镇上,给乖孩子送上小礼物,而顽皮的孩子则得到一个土豆。
在冰岛的一个小镇上,有一条街道上有 $N$ 栋房子,编号依次为 $1$ 到 $N$。每栋房子都用圣诞灯装饰得非常漂亮,起初这些灯全都亮着。
在圣诞节前的每个晚上,会有一位尤拉兄弟光临这条街道。圣诞节前第 $K$ 个晚上来访的尤拉兄弟非常喜欢数字 $K$,因此他只会拜访编号可以被 $K$ 整除的房子。此外,尤拉兄弟们很顽皮,会切换每个被拜访房子的圣诞灯的状态(即如果灯亮着则关掉,灯关着则打开)。
然而,有一些尤拉兄弟生病了,没有来到镇上。在圣诞节当天,除了第一栋房子以外,所有房子的灯都亮着。问有多少尤拉兄弟来到了镇上?
输入格式
第一行输入一个正整数 $N$,表示尤拉兄弟的数量以及街道上的房子数量。
输出格式
输出一个整数,表示来到镇上的尤拉兄弟的数量。可以假设只有一种可能的情况会导致所有房子的灯亮着,除了第 $1$ 号房子的灯。
提示
考虑 $N=6$ 的情况,街道上有六栋房子,圣诞节前的每个晚上发生以下情况(假设没有尤拉兄弟生病):
- 圣诞节前第 $6$ 天:尤拉兄弟会关闭第 $6$ 号房子的灯。
- 圣诞节前第 $5$ 天:尤拉兄弟会关闭第 $5$ 号房子的灯。
- 圣诞节前第 $4$ 天:尤拉兄弟会关闭第 $4$ 号房子的灯。
- 圣诞节前第 $3$ 天:尤拉兄弟会关闭第 $3$ 号房子的灯,并打开第 $6$ 号房子的灯。
- 圣诞节前第 $2$ 天:尤拉兄弟会关闭第 $2$ 和第 $6$ 号房子的灯,并打开第 $4$ 号房子的灯。
- 圣诞节前第 $1$ 天:尤拉兄弟会关闭第 $1$ 和第 $4$ 号房子的灯,并打开第 $2$、$3$、$5$ 和 $6$ 号房子的灯。
然而,第 $4$ 号房子的灯在圣诞节当天是关闭的,与实际情况不符。
如果只有原本应该在圣诞节前第 $4$ 天到来的尤拉兄弟生病了,那么所有灯都将亮着,除了第 $1$ 号房子的灯。正确答案是 $5$:来到镇上的尤拉兄弟是在第 $6$、$5$、$3$、$2$ 和 $1$ 天。
对于所有数据,$N\leq 10^{13}$