题目背景

在数不尽层数的世界中，迷失在回忆中的少女，寻找着不知是否存在的「真实」。

决定了起点和终点后，你能帮助泠珞，找出如何最快地追寻她想要知道的真相呢？

题目描述

有一个 $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}$。