题目描述

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。

小蓝的图由 $X$ 个结点组成，依次编号 $1$ 至 $X$。

对于两个不同的结点 $a,b$，如果 $a$ 和 $b$ 的差的绝对值大于 $Y$，则两个结点之间没有边相连；如果 $a$ 和 $b$ 的差的绝对值小于等于 $Y$，则两个点之间有一条长度为 $a$ 和 $b$ 的最小公倍数的无向边相连。

例如：$Y=21$ 时，结点 $1$ 和结点 $23$ 之间没有边相连；结点 $3$ 和结点 $24$ 之间有一条无向边，长度为 $24$；结点 $15$ 和结点 $25$ 之间有一条无向边，长度为 $75$。

请计算，结点 $1$ 和结点 $X$ 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

输入描述

第一行包一个整数 $N$，表示测试数据的规模。

接下来 $N$ 行每行 $2$ 个整数 $X,Y$。

输出描述

对每个输入输出一个整数表示答案。

3
40 21
2019 21
2021 21

60
7549269
10266837

评测用例规模与约定：

对于所有评测用例，$1≤N≤5，1≤X≤10^4，1≤Y≤100$。