2147. Карточный фокус

Джим работает престидижитатором. Иначе говоря, он фокусник. Основная специализация Джима – карточные фокусы.

Недавно Джим придумал новый карточный фокус. Изначально для фокуса берется колода из `n` различных карт. После этого зритель выбирает одну карту из колоды, запоминает ее, возвращает в колоду и тщательно перемешивает карты.

И тут начинается магическое действие. Джим берет перемешанную колоду карт так, чтобы карты находились рубашкой вверх. Затем он раскладывает карты из колоды по `m` кучкам, причем верхняя карта колоды попадает в первую кучку, вторая сверху – во вторую, `(m\ +\ 1)`-я карта, если такая есть в колоде, попадает снова в первую кучку, `(m\ +\ 2)`-я во вторую и т.д. После этого Джим спрашивает зрителя, в какой из кучек находится загаданная зрителем карта. Пусть карта попала в `i`-ую кучку. После этого Джим собирает кучки карт обратно в одну колоду. При этом `i`-ая кучка оказывается сверху новой колоды, под ней `(i\ +\ 1)`-я и так до `n`-й, после которой следует первая кучка и так до `(i\ -\ 1)`-й. При этом порядок карт в каждой кучке сохраняется, то есть первая карта, положенная в кучку оказывается верхней в кучке, вторая – под ней. Повторяя данные операции несколько раз, через некоторое время Джим говорит, что путем магии и волшебства добился того, чтобы загаданная карта оказалась верхней в колоде. И карта действительно оказывается верхней.

Рассмотрим пример такого фокуса. Пусть `n\ =\ 6` и карты обозначаются числами от `1` до `6`, а `m\ =\ 2`. Пусть зритель загадал карту `1`, а помешанная колода имеет вид `(4,\ 2,\ 1,\ 5,\ 6,\ 3)`. При первом раскладывании по кучкам получаются кучки `(4,\ 1,\ 6)` и `(2,\ 5,\ 3)`, после чего Джим собирает из этих кучек колоду `(4,\ 1,\ 6,\ 2,\ 5,\ 3)`. На следующем шаге кучки `(4,\ 6,\ 5)` и `(1,\ 2,\ 3)`, после этого колода имеет вид `(1,\ 2,\ 3,\ 4,\ 6,\ 5)`. И с помощью магии загаданная карта оказалась верхней!

От того, какая карта загадана и как перемешаны карты в колоде, зависит сколько раз надо повторить магическое действие, чтобы найти загаданную карту. Однако существует такое минимальное число `k`, что для любого расположения карты в колоде и любой загаданной карты достаточно повторить раскладывания `k` раз, чтобы загаданная карта оказалась верхней.

Напишите программу, которая по данным `n` и `m` найдет минимальное `k`.

В первой строке входного файла два целых числа `n` и `m` (`2\ ≤\ m\ ≤\ n\ ≤\ 10^{9}`).

В выходной файл выведите единственное число `k` – минимальное число раскладываний, которое необходимо совершить, чтобы загаданная карта точно оказалась сверху колоды.

6 2

3

21 3

3