Let $B$ be a positive integer. A natural number $n$ is called $B$-smooth, if in its factorisation into primes there is no prime factor greater then $B$. We may say equivalently that a number n is called $B$-smooth, if it may be represented as a product of positive integers less then or equal to $B$.

Task

Write a program which:

• reads from the standard input three positive integers $n$, $m$ and $B$,
• determines the number of all $B$-smooth numbers in the interval $[n,n+m]$ (inclusive),
• writes the result to the standard output.

Input

In the first line of the standard input there are three integers $n$, $m$ and $B$, separated by single spaces, $1 \le n \le 2\,000\,000\,000$, $1 \le m \le 100\,000\,000$, $1 \le B \le 1\,000\,000$.

Output

Your program should write one integer in the first line of the standard output. It should be the determined number of B-smooth numbers.

Example

Input

30 10 5

Output

4