P10869 [HBCPC2024] LCMs

Walk Alone has a number axis with only positive integers on it. The cost of walking from point on integer $a$ to point on integer $b$ is ${\rm lcm}(a, b)$, where ${\rm lcm}(a, b)$ means the least common multiple of integers $a$ and $b$. Due to the hatred of the integer $1$, Walk Alone forbids anyone from moving to points on integers $\textbf{smaller than or equal to}$ $1$. Given two integers $a$ and $b$, you need to calculate the minimal cost of walking from point on integer $a$ to $b$.

There are $T$ ($1 \le T \le 1000$) test cases. In each test case, there is only one line containing two integers $a$ and $b$ ($2 \le a \le b \le 10^7$), denoting the start and end point.

For each test case, output a single integer denoting the minimal cost.

In the first test case, you can walk such a path: $3 \to 2 \to 4$, where the total cost is ${\rm lcm}(3, 2) + {\rm lcm}(2, 4) = 6 + 4 = 10$, which can be proved to be the minimum.