311038: CF1925B. A Balanced Problemset?

B. A Balanced Problemset?time limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Jay managed to create a problem of difficulty $x$ and decided to make it the second problem for Codeforces Round #921.

But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of $n$ sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to $x$.

The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset.

Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.

Input

The first line of input contains a single integer $t$ ($1\leq t\leq 10^3$) denoting the number of test cases.

Each test case contains a single line of input containing two integers $x$ ($1\leq x\leq 10^8$) and $n$ ($1\leq n\leq x$).

Output

For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.

ExampleInput

3
10 3
5 5
420 69

Output

2
1
6

Note

For the first test case, one possible way is to break up the problem of difficulty $10$ into a problemset having three problems of difficulties $4$, $2$ and $4$ respectively, giving a balance equal to $2$.

For the second test case, there is only one way to break up the problem of difficulty $5$ into a problemset of $5$ problems with each problem having a difficulty $1$ giving a balance equal to $1$.

题目大意：
Jay创建了一个难度为x的问题，并决定将其作为Codeforces第921轮比赛的第二个问题。但Yash担心这个问题会使比赛非常不平衡，导致协调员拒绝它。因此，他决定将这个问题分解为n个子问题，使得所有子问题的难度都是正整数，并且它们的总和等于x。协调员Aleksey定义问题集的平衡度为所有子问题难度的最大公约数（GCD）。如果Yash选择子问题的难度最优化，求他能达到的最大平衡度。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^3），表示测试用例的数量。
每个测试用例包含一行，包含两个整数x（1≤x≤10^8）和n（1≤n≤x）。

输出：
对于每个测试用例，打印一行，包含一个整数，表示Yash能实现的问题集的最大平衡度。

示例：
输入：
3
10 3
5 5
420 69

输出：
2
1
6

注意：
对于第一个测试用例，一种可能的方法是将难度为10的问题分解为一个问题集，该问题集有三个问题，难度分别为4、2和4，从而得到平衡度等于2。
对于第二个测试用例，将难度为5的问题分解为5个问题集的唯一方法是每个问题难度为1，得到平衡度等于1。题目大意： Jay创建了一个难度为x的问题，并决定将其作为Codeforces第921轮比赛的第二个问题。但Yash担心这个问题会使比赛非常不平衡，导致协调员拒绝它。因此，他决定将这个问题分解为n个子问题，使得所有子问题的难度都是正整数，并且它们的总和等于x。协调员Aleksey定义问题集的平衡度为所有子问题难度的最大公约数（GCD）。如果Yash选择子问题的难度最优化，求他能达到的最大平衡度。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^3），表示测试用例的数量。 每个测试用例包含一行，包含两个整数x（1≤x≤10^8）和n（1≤n≤x）。 输出： 对于每个测试用例，打印一行，包含一个整数，表示Yash能实现的问题集的最大平衡度。 示例： 输入： 3 10 3 5 5 420 69 输出： 2 1 6 注意： 对于第一个测试用例，一种可能的方法是将难度为10的问题分解为一个问题集，该问题集有三个问题，难度分别为4、2和4，从而得到平衡度等于2。 对于第二个测试用例，将难度为5的问题分解为5个问题集的唯一方法是每个问题难度为1，得到平衡度等于1。