Description

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

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

As everyone knows, the watch has only 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 increments the current number by k..."

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

Note: When pressing the +k button, if incrementing by 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 the time to 2.

Input Format

A single 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

A single integer

Representing the maximum number of button presses required to adjust from any time to any other time, 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