410523: GYM104034 3 Лука наблюдает за кузнечиками

3. Лука наблюдает за кузнечикамиограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Любимое занятие Луки — наблюдать за кузнечиками. Сегодня утром, прогуливаясь по парку, он обнаружил кузнечика, который прыгал по окружности длиной $$$n$$$ метров.

Лука заметил, что за один прыжок кузнечик может переместиться по часовой стрелке на $$$k$$$ или $$$k + 1$$$ метров от своей текущей позиции на окружности. Мальчику стало интересно, какое минимальное количество прыжков потребуется кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — длина окружности в метрах.

Вторая строка содержит одно целое число $$$k$$$ ($$$1 \le k \le 10^9$$$) — характеристика длины прыжка кузнечика в метрах.

Гарантируется, что $$$1 \le n \cdot k \le 10^9$$$.

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

Выведите одно целое число — минимальное количество прыжков, которое придется сделать кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.

Система оценки

Решения, правильно работающие только для случаев, когда $$$n$$$ не превосходит $$$100$$$, будут оцениваться в $$$60$$$ баллов.

ПримерыВходные данные

10
3

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

3

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

10
1

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

5

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

11
7

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

3

Примечание

Рассмотрим первый пример из условия. Один из вариантов действий кузнечика таков:

1. Выполнить прыжок длины $$$3$$$,
2. Выполнить прыжок длины $$$4$$$,
3. Выполнить прыжок длины $$$3$$$.

Таким образом, суммарно кузнечик преодолеет $$$3 + 4 + 3 = 10$$$ метров, то есть вернется в исходную точку.

Во втором примере из условия кузнечику достаточно выполнить пять прыжков длины $$$2$$$.

В третьем примере из условия можно выполнить один прыжок длины $$$8$$$ и два прыжка длины $$$7$$$. Таким образом, суммарно кузнечик преодолеет $$$8 + 7 + 7 = 22$$$ метра, то есть обойдет окружность дважды и вернется в исходную точку.