小H正在研究两个正整数 X 和 Y 的性质。他定义了一套变换规则，允许他对这两个数进行任意次（包括零次）以下操作：
约去公因子： 计算 X 和 Y 的最大公约数 G，然后令 X = X / G, Y = Y / G。
因子转移（X到Y）： 选择 X 的一个任意因子 R (即 R 整除 X 且 1 < R < X)，然后令 X = X / R, Y = Y * R。
因子转移（Y到X）： 选择 Y 的一个任意因子 R (即 R 整除 Y 且 1 < R < Y)，然后令 Y = Y / R, X = X * R。
小H的目标是：通过巧妙运用这些操作（或者完全不操作），找到一种方式，使得最终得到的 X 与 Y 两数之和 X + Y 尽可能小。他想知道，当和达到最小值时，两数之和为多少？
输入描述:
第一行包含一个正整数T，代表数据组数（1<=T<=500）。
接下来T行，每行代表一组测试数据，包含两个正整数X和Y（1<=X,Y<=109）。
输出描述:
对于每组数据，输出一行，包含一个正整数，代表X和Y的和。