B. 平衡的问题集？
每测试点时间限制：1.5 秒
每测试点内存限制：256 兆字节

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

但 Yash 担心这道题会让比赛变得非常不平衡，导致协调员拒绝接受。于是，他决定将这道题拆分成一个包含 $n$ 个子题的问题集，要求所有子题的难度都是正整数，并且它们的难度之和等于 $x$。

协调员 Aleksey 定义问题集的平衡度为所有子题难度的最大公约数（GCD）。

如果 Yash 可以最优地选择子题的难度，请找出他能够获得的最大平衡度。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。
每个测试用例一行，包含两个整数 $x$（$1 \le x \le 10^8$）和 $n$（$1 \le n \le x$）。

输出
对于每个测试用例，输出一行一个整数，表示 Yash 能获得的最大平衡度。

示例
输入：

3
10 3
5 5
420 69

输出：

2
1
6

说明

• 对于第一个测试用例：一种可行的拆分方式是将难度为 $10$ 的题目拆成三个子题，难度分别为 $4$、$2$、$4$，此时平衡度为 $2$。
• 对于第二个测试用例：只有一种方式将难度为 $5$ 的题目拆成 $5$ 个子题，每个子题难度为 $1$，平衡度为 $1$。