Поликарп хочет купить ровно \(n\) лопат. В магазине продаются упаковки с лопатами. Всего в магазине \(k\) различных видов упаковок — упаковка \(i\)-го вида состоит из \(i\) лопат (\(1 \le i \le k\)). В магазине есть бесконечное количество упаковок каждого вида.
Поликарп хочет выбрать один вид упаковки и после этого купить несколько (одну или более) упаковок этого вида. Какое наименьшее количество упаковок придется купить Поликарпу, чтобы суммарно купить ровно \(n\) лопат?
Например, если \(n=8\) и \(k=7\), то Поликарп купит \(2\) упаковки из \(4\) лопат.
Помогите Поликарпу найти минимальное количество упаковок, которое необходимо купить при условии, что он:
- суммарно купит ровно \(n\) лопат;
- размеры всех купленных им упаковок одинаковы и являются целым числом от \(1\) до \(k\) включительно.
Выходные данные
Выведите \(t\) ответов на наборы тестовых данных. Каждый ответ является целым положительным числом — минимальным количеством упаковок.
Примечание
Ответ на первый набор тестовых данных разобран в условии.
Во втором наборе существует только один способ купить \(8\) лопат — \(8\) упаковок по одной лопате.
В третьем наборе нужно купить \(1\) упаковку из \(6\) лопат.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8 7
8 1
6 10
999999733 999999732
999999733 999999733
|
2
8
1
999999733
1
|