Jim works as a prestige man. In other words, he is a magician. Jim's main specialty is card tricks.

Jim recently came up with a new card trick. Initially, a deck of $$$n$$$ different cards is taken for the trick. After that, the spectator selects one card from the deck, remembers it, returns to the deck and carefully shuffles the cards.

And this is where the magic begins. Jim takes a shuffled deck of cards so that the cards are face down. Then he arranges the cards from the deck into $$$m$$$ piles, with the top card of the deck going into the first pile, the second from the top into the second, $$$m + 1$$$th card, if there is one in the deck, it goes back to the first pile, $$$m + 2$$$th to the second, and so on. After that, Jim asks the spectator which of the piles contains the card that the spectator has guessed. Let the card be in the $$$i$$$-th pile. After that, Jim collects the piles of cards back into one deck. In this case, the $$$i$$$-th heap is on top of the new deck, under it is the $$$i + 1$$$-th, and so on up to the $$$n$$$-th, after which the first heap follows, and so on up to $$$i - 1$$$-th. At the same time, the order of the cards in each pile is preserved, that is, the first card placed in the pile is the top one in the pile, the second is below it. Repeating these operations several times, after a while Jim says that by magic and sorcery he has achieved the hidden card was the top one in the deck. And the card really is the top one.

Consider an example of such a trick. Let $$$n = 6$$$ and cards are denoted by numbers from $$$1$$$ to $$$6$$$, and $$$m = 2$$$. Let the spectator guess the card $$$1$$$, and the crazy deck has the form $$$(4, 2, 1, 5, 6, 3)$$$. The first heaping results in heaps $$$(4, 1, 6)$$$ and $$$(2, 5, 3)$$$, after which Jim collects a deck of $$$(4, 1, 6, 2, 5, 3)$$$ from these piles. At the next step, heaps of $$$(4, 6, 5)$$$ and $$$(1, 2, 3)$$$, after that the deck looks like $$$(1, 2, 3, 4, 6, 5)$$$. And with the help of magic, the hidden card turned out to be the top one!

It depends on which card is hidden and how the cards are mixed in the deck, how many times you need to repeat the magical action to find the hidden card. However, there is such a minimum number $$$k$$$ that for any arrangement of the card in the deck and any hidden card, it is enough to repeat the unfolding $$$k$$$ times for the hidden card to be the top one.

Write a program that, given $$$n$$$ and $$$m$$$, finds the minimum $$$k$$$.