题目背景

数据为洛谷自造。

题目描述

Adleman 非常喜欢数学，最近他遇到了一个棘手的问题：对于一个正整数 $A$，Adleman 发现一些自然数的质因子分解式中没有大于 $A$ 的因子，这样的自然数非常的特殊。Adleman 想知道对于给定的正整数 $A$，一个区间 $[N, N+M]$ 内所有满足上述条件的自然数的个数。

输入格式

$3$ 个用空格分开的整数 $N,M,A$。

输出格式

一个整数，表示对于给定的正整数 $A$，区间 $[N, N+M]$ 内特殊自然数的个数。

30 10 5

4

提示

样例解释

$[30, 40]$ 之间的数质因子分解式如下：

• $30=2\times 3\times 5$
• $31=1\times 31$
• $32=2\times 2\times 2\times 2\times 2$
• $33=3\times 11$
• $34=2\times 17$
• $35=5\times 7$
• $36=2\times 2\times 3\times 3$
• $37=1\times 37$
• $38=2\times 19$
• $39=3\times 13$
• $40=2\times 2\times 2\times 5$

其中 $30,32,36,40$ 的质因子分解式中没有大于 $5$ 的因子，所以一共有 $4$ 个。

数据范围

• $50\%$ 的数据满足：$1\leq N,M,A\leq 5000$；
• $100\%$ 的数据满足：$1\leq N,M,A≤50\,000$；