Description

Xiao Ming bought a high-end, sophisticated electronic watch and is preparing to set the time.

In the M78 nebula, the units for measuring time are different from those on Earth. One hour in the M78 nebula consists of n minutes.

As everyone knows, the watch only has one button to increment the current number by 1. When adjusting the minutes, if the current display shows 0, pressing the button once will change it to 1, and pressing it again will change it to 2. If the current number is n - 1, pressing the button once will change it to 0.

Being a perfectionist, Xiao Ming must set the watch to the correct time. If the watch's time is 1 minute ahead of the current time, he would need to press the increment button n - 1 times to adjust it back to the correct time.

Xiao Ming thought, how great it would be if the watch could have an additional button that adds k to the current number...

He wants to know, with this +k button, what the maximum number of button presses would be required to adjust from any minute to any other minute, following the optimal strategy.

Note: When pressing the +k button, if adding k results in a number exceeding n - 1, it will wrap around using modulo n.

For example, when n = 10 and k = 6, if the current time is 0, pressing the +k button twice will adjust it to 2.

Input Format

One line containing two integers, n and k, as described in the problem.

For 20% of the data, 0 < k < n <= 5

For 60% of the data, 0 < k < n <= 100

For 100% of the data, 0 < k < n <= 100000

Output Format

One line containing an integer.

This integer represents the maximum number of button presses required to adjust from one time to another, following the optimal strategy.

```output1
2

Hint

If the time is already correct, press 0 times. Otherwise, the relationship between the number of presses and the operation sequence is as follows:

1: +1

2: +1, +1

3: +3

4: +3, +1

Source

Final exam questions from the 9th Lanqiao Cup C/C++ Group B National Competition in 2018