Студент Миша увлекся карточными фокусами, но, к сожалению, так и не сумел научиться профессионально перемешивать карты. Так как учится он на программиста, то для перемешивания карт он составил следующий алгоритм:

1. Колода карт кладется на стол, рубашкой вверх.
2. Карты снимаются по одной с верха колоды и раскладываются по очереди в $$$k$$$ кучек: первая карта – в первую, вторая – во вторую, третья в третью, ..., $$$k$$$-я в $$$k$$$-ю, $$$(k+1)$$$-я снова в первую, $$$(k+2)$$$-я во вторую и так далее.
3. Новая карта кладется сверху тех карт, что уже лежат в кучке, то есть карта с номером $$$k+1$$$ ляжет на первую.
4. Когда все карты разложены, кучи снова объединяют в колоду: первую кучу кладут поверх второй, вторую – поверх третьей, и так далее. В самом низу оказывается последняя $$$k$$$-я куча.
5. Полученная таким образом колода считается перемешанной.

Например, пусть у нас есть колода из $$$10$$$ карт, пронумерованных от $$$0$$$ до $$$9$$$, тогда после перемешивания с помощью $$$3$$$-х кучек получим следующий порядок карт (сверху вниз) « 9, 6, 3, 0, 7, 4, 1, 8, 5, 2 »:

Пытаясь улучшить перемешивание, Миша применял этот алгоритм несколько раз подряд и, к своему удивлению, обнаружил, что последовательное применение данного алгоритма в конце концов всегда приводит карты в первоначальный порядок. От количества начальных карт $$$n$$$ и количества используемых куч $$$k$$$ зависит только количество применений алгоритма, когда все вернется к исходному порядку. А если выбрать $$$n = k$$$, то порядок карт вообще не меняется.

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