D. Покупка лопат
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп хочет купить ровно $$$n$$$ лопат. В магазине продаются упаковки с лопатами. Всего в магазине $$$k$$$ различных видов упаковок — упаковка $$$i$$$-го вида состоит из $$$i$$$ лопат ($$$1 \le i \le k$$$). В магазине есть бесконечное количество упаковок каждого вида.

Поликарп хочет выбрать один вид упаковки и после этого купить несколько (одну или более) упаковок этого вида. Какое наименьшее количество упаковок придется купить Поликарпу, чтобы суммарно купить ровно $$$n$$$ лопат?

Например, если $$$n=8$$$ и $$$k=7$$$, то Поликарп купит $$$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$$$ ответов на наборы тестовых данных. Каждый ответ является целым положительным числом — минимальным количеством упаковок.

Пример
Входные данные
5
8 7
8 1
6 10
999999733 999999732
999999733 999999733
Выходные данные
2
8
1
999999733
1
Примечание

Ответ на первый набор тестовых данных разобран в условии.

Во втором наборе существует только один способ купить $$$8$$$ лопат — $$$8$$$ упаковок по одной лопате.

В третьем наборе нужно купить $$$1$$$ упаковку из $$$6$$$ лопат.