Card Trick

Jim is a magician. More precisely, he is a card magician, and card tricks are his main specialty.

Jim recently invented a new card trick. At the start, the trick uses a deck of $n$ distinct cards. Then a spectator picks one card from the deck, memorizes it, puts it back, and the deck is shuffled carefully.

The magic starts here. Jim takes the shuffled deck with the cards face down. Then he deals the cards into $m$ piles: the top card goes to pile 1, the second card from the top goes to pile 2, the $(m+1)$-th card, if it exists, goes to pile 1 again, the $(m+2)$-th to pile 2, and so on. Jim then asks the spectator which pile contains the chosen card. Suppose the card is in pile $i$. Jim collects the piles back into one deck. Pile $i$ goes on top of the new deck, with pile $i+1$ under it, and so on up to pile $n$, after which comes pile 1, up to pile $i-1$. The order of the cards inside each pile is kept, so the first card dealt into a pile is the top card of that pile, the second is under it.

Jim repeats these operations several times until the chosen card is on top of the deck. He claims the card is on top through magic, and it really is on top.

For example, let $n = 6$, the cards are numbered 1 to 6, and $m = 2$. The spectator chose card 1, and the shuffled deck is $(4, 2, 1, 5, 6, 3)$. The first deal gives piles $(4, 1, 6)$ and $(2, 5, 3)$, and collecting them gives the deck $(4, 1, 6, 2, 5, 3)$. The next step gives piles $(4, 6, 5)$ and $(1, 2, 3)$, and the deck becomes $(1, 2, 3, 4, 6, 5)$. The chosen card 1 is now on top!

How many times the operation must be repeated depends on the chosen card and on the order of the cards in the deck. Still, there is a minimum number $k$ such that for any position of the card in the deck and any chosen card, repeating the deal $k$ times puts the chosen card on top.

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

The first line contains two integers $n$ and $m$ ($2 \le m \le n \le 10^{9}$).

Print a single number $k$, the minimum number of deals needed so that the chosen card is certainly on top of the deck.