← 返回题目列表

Codeforces · 1925/B

B. 平衡的问题集?

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

Jay 设法创建了一个难度 $$$x$$$ 的问题,并决定将其作为 Codeforces Round #921 的第二个问题。

但Yash担心这个问题会让比赛变得高度不平衡,协调员会拒绝它。因此,他决定将其分解为由$$$n$$$个子问题组成的问题集,使得所有子问题的难度都是正整数,并且它们的总和等于$$$x$$$。

协调员 Aleksey 将问题集的平衡定义为问题集中所有子问题的难度的 GCD。

求Yash在最优选择子问题难度的情况下可以达到的最大平衡。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^3$$$) 表示测试用例的数量。

每个测试用例包含一行输入,其中包含两个整数 $$$x$$$ ($$$1\leq x\leq 10^8$$$) 和 $$$n$$$ ($$$1\leq n\leq x$$$)。

输出

对于每个测试用例,打印一行,其中包含一个整数,表示 Yash 可以实现的问题集的最大平衡。

示例

输入 #1

3
10 3
5 5
420 69

输出 #1

2
1
6

注意

对于第一个测试用例,一种可能的方法是将难度 $$$10$$$ 的问题分解为一个问题集,其中三个难度问题分别为 $$$4$$$、$$$2$$$ 和 $$$4$$$,给出的余额等于 $$$2$$$。

对于第二个测试用例,只有一种方法可以将难度 $$$5$$$ 的问题分解为 $$$5$$$ 问题的问题集,每个问题的难度为 $$$1$$$,平衡等于 $$$1$$$。