29495번 - Карточный фокус 다국어

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

Недавно Джим придумал новый карточный фокус. Изначально для фокуса берется колода из $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 \le m \le n \le 10^{9}$).

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