L. LCMs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 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$$$.

Input

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.

Output

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

Example
Input
3
3 4
10 15
2 4
Output
10
25
4
Note

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.