در شهر اعداد، دو عدد $p$ و $q$ وجود دارند . عدد $p$ نسبت به عدد $q$ حسودی میکند ، چون فکر میکند تعداد بیشتری عدد وجود دارد که بزرگترین توان $q$ آنها بیشتر از بزرگترین توان $p$ آنهاست. ما به کمک شما احتیاج داریم تا به $p$ اثبات کنیم که حرف او لزوماً درست نیست.
فرض کنید $f(a,b)$ برابر با بزرگترین $(t \geq 0)$ باشد که $a$ بر $b^t$ بخشپذیر باشد. به عدد $x$ میگوییم خوب اگر $f(x,p)$ بیشتر از $f(x,q)$ باشد.
به شما چهار عدد $a$، $b$، $p$ و $q$ داده شده است ، شما باید تعداد اعداد خوب بزرگتر یا مساوی $a$ و کمتر یا مساوی $b$ را بیابید.
در سطر اول ورودی چهار عدد $1 \leq a \leq b \leq 10^{18}$ و $2 \leq p, q \leq 10^9$ آمده است.
در تنها سطر خروجی پاسخ سوال را چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 1 20 3 2 | 4 |