题目描述

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.

3
3 4
10 15
2 4

10
25
4

提示

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.