题目描述

Walk Alone 有一个数轴，上面只有正整数。从整数 $a$ 走到整数 $b$ 的代价是 ${\rm lcm}(a, b)$，其中 ${\rm lcm}(a, b)$ 表示整数 $a$ 和 $b$ 的最小公倍数。由于对整数 $1$ 的厌恶，Walk Alone 禁止任何人移动到小于或等于 $1$ 的整数点上。

给定两个整数 $a$ 和 $b$，你需要计算从整数 $a$ 到 $b$ 的最小行走代价。

输入格式

有 $T$ 个测试用例（$1 \le T \le 1000$）。

在每个测试用例中，只有一行包含两个整数 $a$ 和 $b$（$2 \le a \le b \le 10^7$），表示起点和终点。

输出格式

对于每个测试用例，输出一个整数，表示最小代价。

3
3 4
10 15
2 4

10
25
4

提示

在第一个测试用例中，你可以选择这样的路径：$3 \to 2 \to 4$，总代价为 ${\rm lcm}(3, 2) + {\rm lcm}(2, 4) = 6 + 4 = 10$，这可以被证明是最小的。（由 ChatGPT 4o 翻译）