Codeforces Round 921 (Div. 2) |
---|
Закончено |
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.
310 35 5420 69
2 1 6
В первом наборе входных данных один из возможных способов разбить задачу сложности $$$10$$$ на набор из трех подзадач сложности $$$4$$$, $$$2$$$ и $$$4$$$ соответственно, дает сбалансированность $$$2$$$.
Во втором наборе входных данных существует единственный способ разбить задачу сложности $$$5$$$ на набор из $$$5$$$ подзадач, взяв все их сложности по $$$1$$$, дает сбалансированность $$$1$$$.
Название |
---|