微观戏剧
题目背景
$$
\begin{array}{cr}
\text{不 我不会说 那愚蠢的诅咒}\\
\text{因为你和我 都不被神明保佑}\\
\text{跃动着右心而降生的我}\\
\text{将一切标为}\overset{\text{Unaccepted}}{\text{不接受}}\\
&\text{——《微观戏剧》}
\end{array}
$$
---
在数不尽层数的世界中，迷失在回忆中的少女，寻找着不知是否存在的「真实」。
决定了起点和终点后，你能帮助泠珞，找出如何最快地追寻她想要知道的真相呢？
题目描述
有一个 $10^{100}$ 个结点的无向图，结点从 $1$ 到 $10^{100}$ 编号，每对结点 $u$ 与结点 $v$ 之间都有一条长度为 $\operatorname{lcm}(u,v)$ 的边连接。$\operatorname{lcm}(u,v)$ 是指 $u$ 和 $v$ 的最小公倍数，即最小的能被 $u$ 和 $v$ 同时整除的正整数。
有 $q$ 次询问，每次给定 $x,y$，问结点 $x$ 到结点 $y$ 的最短路径长度是多少。
输入输出格式
输入格式
第一行一个正整数 $q$。
接下来 $q$ 行，每行两个正整数 $x,y$。
输出格式
对于每组询问，一行一个非负整数表示答案。
输入输出样例
输入样例 #1
4
3 6
1 4
2 5
314652 314652输出样例 #1
6
4
7
0说明
**【样例 #1 解释】**
对于第一组数据，最优路径是 $3\to 6$，路径长度为 $\operatorname{lcm}(3,6)=6$。可以证明**不存在**更短的路径。
**【数据范围】**
**本题采用捆绑测试**。
对于 $100\%$ 的数据，$1\le q\le 2\times10^5$，$1\le x,y\le 1\times10^{18}$。
| 子任务编号 | 分值 | $q\le $ | $x,y\le $ |
| :-----------: | :-----------: | :-----------: | :-----------: |
| $1$ | $2$ | $1$ | $5$ |
| $2$ | $5$ | $1$ | $3\times10^3$ |
| $3$ | $17$ | $100$ | $2\times10^5$ |
| $4$ | $29$ | $2\times10^5$ | $1\times10^9$ |
| $5$ | $47$ | $2\times10^5$ | $1\times10^{18}$ |