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$$$。