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

---

علی که حوصله اش از قطعی اینترنت سر رفته، برای خودش یک بازی یک نفره‌ی بسیار سرگرم کننده طرح کرده است. در این بازی، او ابتدا به یک سایت تولید عدد تصادفی ملی می‌رود، و یک عدد تصادفی مثل $n$ دریافت می‌کند. حال بازی شروع می‌شود و در هر مرحله او یک عدد طبیعی بزرگتر از ١ مثل $x$ را انتخاب می‌کند به طوری که $n$ بر $x$ بخش پذیر باشد، و $n$ را با $\frac{n}{x}$ جایگزین می‌کند. او این کار را تا زمانی که $n \neq 1$ است ادامه می‌دهد. علی دوست دارد تعداد مراحل بازی بیشینه شود تا حوصله اش کمتر سر رود. می‌دانیم عدد $n$ به شکل $\frac{a!}{b!}$ قابل نمایش است که در آن $a$ و $b$ اعدادی صحیح و مثبت هستند. با توجه به هیجان انگیز بودن بازیِ علی، دوستان او هم تصمیم گرفته‌اند این بازی را انجام بدهند. شما باید با دریافت تعدادی $n$ از ورودی، به ازای هر $n$ حداکثر تعداد مراحلی که یک نفر می‌تواند بازی را ادامه دهد را در خروجی چاپ کند.

ورودی

در ورودی ابتدا عدد $k$ می‌آید که نشان دهنده‌ی تعداد بازی‌هاست. سپس در هر یک از $k$ خط بعدی دو عدد $a$ و $b$ می‌آیند، که مقادیر خط $i$ام مربوط به بازی $i$ام هستند.

$$1 \leq k \leq 10^5$$ $$1 \leq b \leq a \leq 10^6$$

خروجی

شما باید $k$ خط خروجی تولید کنید که در خط $i$ام حداکثر تعداد مراحلی که بازی $i$ام می‌تواند طول بکشد نوشته شده باشد.

مثال‌ها

ورودی نمونه ۱

2
3 1
6 3

خروجی نمونه ۱

2
5