408098: GYM102985 E Food Donations

Kumar overestimated demand for his Chicken Biryani and has $$$n$$$ packaged, ready-to-eat parcels of biryani leftover. In order to not waste any food, he packs all the remaining food into his truck and sets out to donate them to different food shelters across the city. While packing them, he realizes that $$$n$$$ is too big to represent as a traditional integer but he realizes that he can write $$$n$$$ as $$$a!/b!$$$ for integers $$$a$$$ and $$$b$$$ where $$$a \geq b$$$ (Note: $$$x!$$$ is defined as the product of all positive integers less than or equal to $$$x$$$).

At each food shelter he visits, if he has $$$k$$$ remaining parcels of food, he will choose some integer divisor of $$$k$$$, $$$x$$$, such that $$$x > 1$$$ and donate $$$k - \frac{k}{x}$$$ parcels of food to that shelter (so he is left with $$$\frac{k}{x}$$$). When $$$k = 1$$$, he will drive home and save the last parcel for himself.

Kumar wants to donate to as many places as he can, so he wants you to figure out, given $$$n$$$ (the number of parcels he has at the start), what is the maximum number of food shelters he can donate to (once he leaves a place he will never come back to it; assume there are at least as many food shelters as the maximum amount he can reach).

The first line of input contains a single line of input $$$t$$$, representing the number of different values of $$$n$$$ that Kumar wants to know the answer for ($$$1 \leq t \leq 10^{6}$$$).

Then, $$$t$$$ lines of input follow with each line containing two space-separated integers $$$a$$$ and $$$b$$$ ($$$1 \leq b \leq a \leq 5 \cdot 10^{6}$$$) where $$$n = a!/b!$$$.

Note: Due to the size of the input, regular Python Input/Output functions may be too slow for this problem.

For each of the $$$t$$$ test cases, output a single line containing a single integer representing the maximum number of food shelters that Kumar could donate to for that value of $$$n$$$.

1
3 1

2

2
6 3
100 21

5
201