در شهر اعداد، دو عدد ‎$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$‎ آمده است.‎

در تنها سطر خروجی پاسخ سوال را چاپ نمایید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد