CF1360D Buying Shovels

Polycarp 想要购买恰好 $n$ 把铲子。商店出售不同类型的铲子包装。商店有 $k$ 种包装类型：第 $i$ 种包装中恰好有 $i$ 把铲子（$1 \le i \le k$）。每种包装类型的数量都是无限的。 Polycarp 想要选择一种包装类型，然后购买若干（至少一个）这种类型的包装。Polycarp 需要买到恰好 $n$ 把铲子，他最少需要买多少包？ 例如，如果 $n=8$ 且 $k=7$，Polycarp 可以购买 $2$ 包，每包 $4$ 把铲子。 请帮助 Polycarp 计算他最少需要购买多少包，要求： - 总共买到恰好 $n$ 把铲子； - 所有购买的包装大小都相同，每包铲子的数量为 $1$ 到 $k$ 之间的整数。

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来有 $t$ 行，每行一个测试用例。 每个测试用例包含两个正整数 $n$（$1 \le n \le 10^9$）和 $k$（$1 \le k \le 10^9$），分别表示铲子的数量和包装类型的数量。

输出 $t$ 行，每行一个正整数，表示每个测试用例中最少需要购买的包装数量。

第一个测试用例的答案已在题目描述中给出。 第二个测试用例中，只有一种方法可以买到 $8$ 把铲子——买 $8$ 包，每包 $1$ 把铲子。 第三个测试用例中，需要买 $1$ 包，每包 $6$ 把铲子。 由 ChatGPT 4.1 翻译