题目背景

$$\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$。

输出格式

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

4
3 6
1 4
2 5
314652 314652

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$		$3\times10^3$
$3$	$17$	$100$	$2\times10^5$
$4$	$29$	$2\times10^5$	$1\times10^9$
$5$	$47$		$1\times10^{18}$