Jay удалось создать задачу сложности \(x\) и он решил сделать ее второй в Codeforces Round #921.
Но Yash опасается, что это сделает раунд несбалансированным, и координатор отклонит её. Чтобы избежать этого, он хочет разбить ее на \(n\) подзадач таким образом, чтобы сложность каждой подзадачи была положительным целым числом, а их сумма была равна \(x\).
Координатор Aleksey определяет сбалансированность набора задач как НОД всех их сложностей.
Найдите максимальную сбалансированность, которую Yash может достичь.
Выходные данные
Для каждого тестового примера выведите одну строку, содержащую одно целое число, обозначающее максимальную сбалансированность набора задач, которую может достичь Yash.
Примечание
В первом наборе входных данных один из возможных способов разбить задачу сложности \(10\) на набор из трех подзадач сложности \(4\), \(2\) и \(4\) соответственно, дает сбалансированность \(2\).
Во втором наборе входных данных существует единственный способ разбить задачу сложности \(5\) на набор из \(5\) подзадач, взяв все их сложности по \(1\), дает сбалансированность \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 3
5 5
420 69
|
2
1
6
|