Statement is not available in English language
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$$$ метра, то есть обойдет окружность дважды и вернется в исходную точку.