← 返回题目列表

Codeforces · 1916/B

B. 两个除数

中文机器翻译题面 查看原题

选择某个数字 $$$1 \le x \le 10^9$$$。给定两个整数 $$$a$$$ 和 $$$b$$$,它们是数字 $$$x$$$ 的两个最大除数。同时满足条件$$$1 \le a < b < x$$$。

对于给定的数字 $$$a$$$, $$$b$$$,您需要找到 $$$x$$$ 的值。

$$$^{\dagger}$$$ 如果存在整数 $$$k$$$ 使得 $$$x = y \cdot k$$$,则数字 $$$y$$$ 是数字 $$$x$$$ 的除数。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的唯一行包含两个整数 $$$a$$$, $$$b$$$ ($$$1 \le a < b \le 10^9$$$)。

保证 $$$a$$$、$$$b$$$ 是某个数字 $$$1 \le x \le 10^9$$$ 的两个最大约数。

输出

对于每个测试用例,输出数字 $$$x$$$,使得 $$$a$$$ 和 $$$b$$$ 是数字 $$$x$$$ 的两个最大约数。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

8
2 3
1 2
3 11
1 5
5 10
4 6
3 9
250000000 500000000

输出 #1

6
4
33
25
20
12
27
1000000000

注意

对于第一个测试用例,所有小于 $$$6$$$ 的除数都等于 $$$[1, 2, 3]$$$,其中最大的两个是 $$$2$$$ 和 $$$3$$$。

对于第三个测试用例,所有小于 $$$33$$$ 的除数都等于 $$$[1, 3, 11]$$$,其中最大的两个是 $$$3$$$ 和 $$$11$$$。

对于第五个测试用例,所有小于 $$$20$$$ 的除数都等于 $$$[1, 2, 4, 5, 10]$$$,其中最大的两个是 $$$5$$$ 和 $$$10$$$。

对于第六个测试用例,所有小于 $$$12$$$ 的除数都等于 $$$[1, 2, 3, 4, 6]$$$,其中最大的两个是 $$$4$$$ 和 $$$6$$$。