Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
пример поиска: Вася Пупкин

# Задача E для тренировки в сентябре

Первоисточник: ACM ICPC 2009 -2010, NEERC, Northern Subregional Contest St Petersburg, October 17, 2009

Задачу добавил: elena

Успешно сдано решений: 2

Problem J. Jealous Numbers

Time limit: 3 seconds
Memory limit: 256 megabytes

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 alpha(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 alpha(n, p) > alpha(n, q). Find out for how many numbers between a and b, inclusive are p-dominating over q.

Input
The first line of the input file contains a, b, p and q (1 <= a <= b <= 10^18; 2 <= p, q <= 10^9; p != q; p and q are prime).

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

Example

input.txt ``` 1 20 3 2 ```
output.txt ``` 4 ```
In the given example 3, 9, 15 and 18 are 3-dominating over 2.