Олимпиадный тренинг

Задача . B. Сбалансированный набор задач?


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.

Примечание

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

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


Примеры
№Входные данныеВыходные данные
1
3
10 3
5 5
420 69
2
1
6
Статистика успешных решений по компиляторам
 Кол-во
С++3