T540661 「YAC Round 12」大空魔术

莲子和梅莉都是秘封俱乐部的成员。这一天，梅莉又做了一个梦，她在梦境中看到了 $+\infty$ 个世界（$+\infty$ 表示正无穷），世界的编号从 $1$ 到 $+ \infty$。 神奇的是，每两个世界之间都有一条双向通道连接。 对于两个不同的世界 $i$ 和 $j$，其之间的通道长度为 $\text{lcm}(i, j)$（$\text{lcm}$ 表示最小公倍数）。 莲子和梅莉想要快速通过这些通道穿梭于这些世界之中。 现在有 $m$ 次询问，每次给定两个世界编号 $x$ 和 $y$，请你求出 $x$ 到 $y$ 的 **最短距离**。

第一行输入一个整数 $m$ （$1 \le m \le 2\times 10^5$），表示询问的个数。 接下来 $m$ 行，每行输入两个整数 $u, v$ （$1 \le x, y \le 10^{18}$），表示每个询问的两个世界编号。

对于每组询问： 输出一行一个非负整数表示答案。

### 样例解释 对于第一个询问，答案为 $\text{lcm}(1, 6) = 6$; 对于第二个询问，编号相同，因此答案为 $0$; 对于第三个询问，答案为 $\text{lcm}(2, 4) = 4$; 对于第四个询问，答案为 $\text{lcm}(1, 3) + \text{lcm}(1, 7) = 10$。