CF1925B.A Balanced Problemset?

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.

杰伊成功设计了一道难度为 $x$ 的题目，并决定将其作为 Codeforces Round #921 的第二题。

但亚什担心这道题会使比赛严重失衡，导致协调员拒绝它。因此，他决定将该题拆分为一个包含 $n$ 道子题的问题集，使得所有子题的难度均为正整数，且它们的难度之和等于 $x$。

协调员阿列克谢将问题集的平衡度定义为该问题集中所有子题难度的最大公约数（GCD）（参见 GCD）。

若亚什能最优地选择各子题的难度，请你求出他所能达到的最大平衡度。

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$).

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

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

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

对于每个测试用例，输出一行，包含一个整数，表示 Yash 能够达到的最大平衡值。

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

对于第一个测试用例，一种可行的方式是将难度为 $10$ 的题目拆分为一个包含三道题的问题集，其难度分别为 $4$、$2$ 和 $4$，从而得到平衡值为 $2$。

对于第二个测试用例，唯一的方式是将难度为 $5$ 的题目拆分为一个包含 $5$ 道题的问题集，每道题的难度均为 $1$，从而得到平衡值为 $1$。