题目描述

小 Z 有一个由除 $1$ 以外的正整数构成的数轴，从点 $x$ 移动到点 $y$ 的代价是 $\operatorname {lcm}(x,y)$，$q$ 次询问给出 $a,b$，求从 $a$ 开始移动到 $b$ 的最小代价。

输入格式

第一行一个整数 $q$。

接下来 $q$ 行每行用空格隔开的两个整数 $a,b$ 表示一次询问。

输出格式

共 $q$ 行每行一个整数表示答案。

3
3 4
10 15
2 4

10
25
4

样例解释 1

第一组询问中，可以这样移动：3 --> 2 --> 4。

数据范围

对于所有数据，$q\le 10000,2\le a<b\le 10^7$

对于前 $30\%$ 的数据，$q\le 3$，$b\le 500$。

对于前 $50\%$ 的数据，$b\le 500$。

另有 $20\%$ 的数据，$a,b$ 不互质。