B. Сбалансированный набор задач?
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Jay удалось создать задачу сложности $$$x$$$ и он решил сделать ее второй в Codeforces Round #921.

Но Yash опасается, что это сделает раунд несбалансированным, и координатор отклонит её. Чтобы избежать этого, он хочет разбить ее на $$$n$$$ подзадач таким образом, чтобы сложность каждой подзадачи была положительным целым числом, а их сумма была равна $$$x$$$.

Координатор Aleksey определяет сбалансированность набора задач как НОД всех их сложностей.

Найдите максимальную сбалансированность, которую Yash может достичь.

Входные данные

В первой строке содержится одно целое число $$$t$$$ ($$$1\leq t\leq 10^3$$$), означающее количество наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей два целых числа $$$x$$$ ($$$1\leq x\leq 10^8$$$) и $$$n$$$ ($$$1\leq n\leq x$$$).

Выходные данные

Для каждого тестового примера выведите одну строку, содержащую одно целое число, обозначающее максимальную сбалансированность набора задач, которую может достичь Yash.

Пример
Входные данные
3
10 3
5 5
420 69
Выходные данные
2
1
6
Примечание

В первом наборе входных данных один из возможных способов разбить задачу сложности $$$10$$$ на набор из трех подзадач сложности $$$4$$$, $$$2$$$ и $$$4$$$ соответственно, дает сбалансированность $$$2$$$.

Во втором наборе входных данных существует единственный способ разбить задачу сложности $$$5$$$ на набор из $$$5$$$ подзадач, взяв все их сложности по $$$1$$$, дает сбалансированность $$$1$$$.