Поликарп хочет купить ровно \(n\) лопат. В магазине продаются упаковки с лопатами. Всего в магазине \(k\) различных видов упаковок — упаковка \(i\)-го вида состоит из \(i\) лопат (\(1 \le i \le k\)). В магазине есть бесконечное количество упаковок каждого вида.
Поликарп хочет выбрать один вид упаковки и после этого купить несколько (одну или более) упаковок этого вида. Какое наименьшее количество упаковок придется купить Поликарпу, чтобы суммарно купить ровно \(n\) лопат?
Например, если \(n=8\) и \(k=7\), то Поликарп купит \(2\) упаковки из \(4\) лопат.
Помогите Поликарпу найти минимальное количество упаковок, которое необходимо купить при условии, что он:
В первой строке записано целое число \(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\) упаковку из \(6\) лопат.
5 8 7 8 1 6 10 999999733 999999732 999999733 999999733
2 8 1 999999733 1
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач