시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB148888.889%

## 문제

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$.

## 입력

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

## 출력

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

## 예제 입력 1

1 20 3 2


## 예제 출력 1

4


## 힌트

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