407018: GYM102687 E Crazy Rich Sean

Hey, it's your friend Crazy Rich Sean! You haven't seen him since the last time you visited Singapore. It turns out he's even crazier and even richer than before. People think that the sign of being rich is being able to afford private jets with caviar and Iberico ham and solid gold toilet seats. The true craziest and richest of society can afford to buy ideas—democracy, truth, and most importantly, numbers.

Crazy Rich Sean bought a shiny new integer sequence. Don't even bother looking for it in the OEIS, since Crazy Rich Sean's team of lawyers has copyrighted, patented, and trademarked this sequence for his exclusive use.

Define the sequence $$$R$$$ as the unique nondecreasing sequence of positive integers $$$R(1), R(2), R(3), \dots$$$ such that for every $$$i \geq 1$$$, $$$i$$$ appears in the sequence exactly $$$R(i) + R(i+1)$$$ times. It starts as: $$$$$$\begin{array}{r|rrrrrrrrrrrrrrrrrrrr} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & \dots \\ \hline R(i) & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 4 & 4 & 4 & 4 & 5 & 5 & 5 & 5 & 5 & 6 & \dots \end{array}$$$$$$

Crazy Rich Sean wants to test out this new integer sequence by playing a game with his employees. Each of his employees has a unique ID number which is some positive integer, and he has an employee for every positive integer. For this game, he announces that all employees whose ID number is between $$$a$$$ and $$$b$$$ (inclusive) must participate. The participating employees must line up in one long queue. An employee with ID number $$$x$$$ is considered safe if (and only if) at least one of the following is true:

• This employee is the first person in the queue.
• If $$$y$$$ is the ID number of the employee directly in front of them in the queue, then $$$\frac{R(y)}{R(x)}$$$ is an integer strictly greater than $$$1$$$.

All employees that are not safe will end up fired. That's awful! Why would Sean do this? Because he's crazy, and rich, and he'll get away with it too, thanks to that aforementioned team of lawyers.

Due to your friendship, Crazy Rich Sean allows one concession—you are allowed to decide the order in which the employees should line up. Among all possible queueing orders, what is the minimum number of employees that will end up fired?

The first line of input contains $$$t$$$, the number of test cases. The following $$$t$$$ lines describe the test cases.

Each test case consists of a single line containing two space-separated integers $$$a$$$ and $$$b$$$.

For each test case, output a single integer denoting the answer for that test case.

For all subtasks

$$$1 \le t \le 4\cdot 10^5$$$

$$$1 \le a \le b \le 2\cdot 10^{18}$$$

Subtask 1 (7 points): $$$b \le 10$$$, $$$t \le 30$$$

Subtask 2 (7 points): $$$b \le 20$$$, $$$t \le 30$$$

Subtask 3 (6 points): $$$b \le 30$$$

Subtask 4 (7 points): $$$b \le 100$$$

Subtask 5 (8 points): $$$b \le 3000$$$, $$$t \le 500$$$

Subtask 6 (20 points): $$$b \le 2\cdot 10^5$$$, $$$t \le 500$$$

Subtask 7 (5 points): $$$b \le 10^6$$$

Subtask 8 (5 points): $$$b \le 2^{32}$$$, $$$t \le 500$$$

Subtask 9 (5 points): $$$b \le 2^{32}$$$

Subtask 10 (5 points): $$$b \le 10^{12}$$$, $$$t \le 500$$$

Subtask 11 (5 points): $$$b \le 10^{12}$$$

Subtask 12 (5 points): $$$b \le 10^{15}$$$, $$$t \le 500$$$

Subtask 13 (5 points): $$$b \le 10^{15}$$$

Subtask 14 (5 points): $$$t \le 500$$$

Subtask 15 (5 points): No additional constraints.

3
1 10
2 5
4 6

6
2
2

Here's one possible queueing order of employees $$$1$$$ to $$$10$$$ (from back to front): $$$$$$7, 4, 10, 1, 5, 2, 9, 3, 6, 8$$$$$$

With this queueing order, you can verify that $$$6$$$ employees will end up getting fired. The only safe employees are employees $$$1$$$, $$$2$$$, $$$4$$$ and $$$8$$$.

It can also be shown that any other queueing order will have $$$6$$$ or more employees end up getting fired. Therefore, the answer for the first sample case is $$$6$$$.