← 返回题目列表

Codeforces · 1360/D

D. 购买铲子

中文机器翻译题面 查看原题

Polycarp 想要购买 $$$n$$$ 铲子。商店出售带铲子的包裹。商店有 $$$k$$$ 类型的包裹:第 $$$i$$$ 类型的包裹恰好由 $$$i$$$ 铲子组成 ($$$1 \le i \le k$$$)。商店里每种类型的包裹都有无限数量。

Polycarp 想要选择一种类型的包,然后购买多个(一个或多个)该类型的包。 Polycarp 最少需要购买多少包才能获得 $$$n$$$ 铲子?

例如,如果 $$$n=8$$$ 且 $$$k=7$$$,则 Polycarp 将购买 $$$2$$$ 包 $$$4$$$ 铲子。

帮助波利卡普找到他需要购买的最少包裹数量,假设他:

- 总共会购买 $$$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$$$ 答案。每个答案都是一个正整数——最小包裹数。

示例

输入 #1

5
8 7
8 1
6 10
999999733 999999732
999999733 999999733

输出 #1

2
8
1
999999733
1

注意

第一个测试用例的答案在声明中进行了解释。

在第二个测试用例中,只有一种方法可以购买 $$$8$$$ 铲子 — 一把铲子的 $$$8$$$ 包。

在第三个测试用例中,您需要购买 $$$1$$$ 包 $$$6$$$ 铲子。