Jealous Numbers#3323

Jealous Numbers

3 seconds
256 megabytes
Easy

There is a trouble in Numberland, prime number is jealous of another prime number . She thinks that there are more integer numbers between and , inclusively, that are divisible by greater power of than that of . Help to get rid of her feelings.

Let \alpha(n, x) be maximal such that is divisible by x^k. Let us say that a number is -dominating over if \alpha(n, p) > \alpha(n, q). Find out for how many numbers between and , inclusive are -dominating over .

Input

The first line of the input file contains , , and (1 \leq a \leq b \leq 10^{18}; 2 \leq p, q \leq 10^9; p \neq q; and are prime).

Output

Output one number - how many numbers between and , inclusive, are -dominating over .

Examples

Example 1

Loading
Loading