Problem Description

$B$ is a positive integer.

If a natural number $n$ is called a B-smooth number, then none of its prime factors is greater than $B$.

We say that a B-smooth number equivalent to $n$ means that it can be represented as a product of positive integers less than or equal to $B$.

Your task is: for the given closed interval $[n, n + m]$, find the number of B-smooth numbers in it.

Input Format

The first line contains three integers $n$, $m$, and $B$.

Output Format

Output the number of B-smooth numbers.

30 10 5

4

Hint

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^9$, $1 \le m \le 10^8$, $1 \le B \le 10^6$.

Translated by ChatGPT 5