题目描述

$B$ 是一个正整数。

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

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

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

输入格式

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

输出格式

求出 B-smooth 数的个数。

30 10 5

4

提示

对于 $100\%$的数据，$1\le n\le 2\times 10^9$， $1\le m\le 10^8$， $1\le B\le 10^6$。