eolymp
bolt
Try our new interface for solving problems
Problems

Jealous Numbers

Jealous Numbers

Time limit 3 seconds
Memory limit 256 MiB

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 x^k. 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 data

The first line of the input file contains a, b, p and q (1ab10^18; 2p, q10^9; pq; p and q are prime).

Output data

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

Examples

Input example #1
1 20 3 2
Output example #1
4