## Problem J. Jealous Numbers ≡

 Author: ACM ICPC 2009-2010, NEERC, Northern Subregional Contest Time limit: 3 sec Input file: jealous.in Memory limit: 256 Mb Output file: jealous.out

### Statement

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

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

### Input file format

The first line of the input file contains a, b, p and q (1 ≤ a ≤ b ≤ 1018; 2 ≤ p, q ≤ 109; p ≠ q; p and q are prime).

In the given example 3, 9, 15 and 18 are 3-dominating over 2.

### Output file format

Output one number — how many numbers n between a and b, inclusive, are p-dominating over q.

### Sample tests

No. Input file (jealous.in) Output file (jealous.out)
1
1 20 3 2
4

0.040s 0.012s 15