Jealous Numbers

문제

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

Let $\alpha (n,x)\backslash alpha(n,\; x)$ be maximal $kk$ such that $nn$ is divisible by $x^{k}x^k$. Let us say that a number $nn$ is $pp$-dominating over~$qq$ if $\alpha (n,p)>\alpha (n,q)\backslash alpha(n,\; p)>\backslash alpha(n,\; q)$. Find out for how many numbers between $aa$ and $bb$, inclusive are $pp$-dominating over~$qq$.

입력

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

출력

Output one number --- how many numbers $nn$ between $aa$ and $bb$, inclusive, are $pp$-dominating over $qq$.

힌트

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