瓦莱拉(Valera)在很平常的一天去上学(工作日他没有其他地方应该去)。在数学课上,他最喜欢的老师埃文斯女士向学生们介绍了除数。尽管瓦莱拉热爱数学,但他对这个特定的话题并不感兴趣。更重要的是,上课太无聊了,他竟然睡着了。而只有一声响亮的放学铃声才能打断他的美梦。
当然,宝贵的资料和老师的讲解都丢失了。然而,瓦莱拉无论如何都必须做足功课。由于他对新材料并不完全了解,他无法自己完成这项工作。这就是为什么他请你帮忙。毕竟你是他最好的朋友,你不能拒绝帮助。
Valera 的家庭任务只有一个问题,虽然以一种非常简单的方式表述,但没有一个简单的解决方案。它的语句如下:如果我们考虑区间 [a;b] 中的所有正整数,那么需要计算该区间中最小除数为某个整数 k 的数字的数量(不必考虑除数等于 1)。换句话说,您应该计算区间 [a;b] 中此类数字的数量,这些数字不能被 2 到 k - 1 之间的任何数字整除,但可以被 k 整除。
输入
第一行也是唯一一行包含三个正整数 a、b、k (1 ≤ a ≤ b ≤ 2·109, 2 ≤ k ≤ 2·109)。
输出
在一行上打印给定问题的答案。
示例
输入 #1
1 10 2
输出 #1
5
输入 #2
12 23 3
输出 #2
2
输入 #3
6 19 5
输出 #3
0
注意
对声明中样本的评论:
在第一个示例中,答案是数字 2、4、6、8、10。
第二个 — 15, 21
第三个中没有这样的数字。