====== Jealous Numbers ====== در شهر اعداد، دو عدد ‎$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 | * [[سوال ۲|سوال بعد]]