[POI2002]B-Smooth 数

题目描述

$B$ 是一个正整数。

如果一个自然数 $n$ 被称为 B-smooth 数,那么它的质因子中没有任何一个超过 $B$。

我们说和 $n$ 等价的一个 B-smooth 数是指它能够表示成小于或等于 $B$ 的正整数乘积。

你的任务是对给定的闭区间 $[n,n+m]$，求出他们中的 B-smooth 数的个数。

输入格式

第一行是三个整数 $n,m$ 和 $B$。

输出格式

求出 B-smooth 数的个数。

样例 #1

样例输入 #1

30 10 5

样例输出 #1

4

提示

对于 $100\%$的数据，$1\le n\le 2 000 000 000$， $1\le m\le 100 000 000$， $1\le B\le 1 000 000$。