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$$$ 铲子。