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 .
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 one number - how many numbers between and , inclusive, are -dominating over .
Example 1