Student Misha became interested in card tricks, but unfortunately, he never managed to learn professional card shuffling. Since he is studying programming, he came up with the following algorithm for shuffling a deck of cards:

1. Place the deck face down on the table.
2. Remove the cards one by one from the top of the deck and distribute them into $$$k$$$ piles in order: the first card goes to the first pile, the second card to the second pile, the third card to the third pile, and so on $$$k$$$-th card to the $$$k$$$-th pile. The $$$(k+1)$$$-th card goes to the first pile, the $$$(k+2)$$$-th to the second, and so forth.
3. When placing a card on a pile, it goes on top of the existing cards in that pile. For example, the $$$(k+1)$$$-th card will be placed on top of the first card in the first pile.
4. Once all cards are distributed, the piles are stacked together to form a new deck: the first pile goes on top of the second, the second on top of the third, and so on, with the last $$$k$$$-th pile at the very bottom.
5. The resulting deck is considered shuffled.

For example, if we have a deck of $$$10$$$ cards numbered from $$$0$$$ to $$$9$$$, shuffling them into $$$3$$$ piles will get the following order: (from top to bottom) " 9, 6, 3, 0, 7, 4, 1, 8, 5, 2 ":

Trying to improve the shuffling, Misha applied this algorithm several times in a row and, to his surprise, found that consistent application of this algorithm always brings the cards back to their original order in the end. Only the number of applications of the algorithm depends on the number of initial cards $$$n$$$ and the number of piles $$$k$$$ used when everything returns to its original order. If $$$n = k$$$, then the order of the cards does not change at all.

To shuffle cards well, Misha wants to determine what minimum number of applications of the algorithm with $$$k$$$ piles a deck of $$$n$$$ cards will return to its original order.