Optimal Button Presses for M78 Clock Adjustment

In the M78 nebula, an hour consists of (n) minutes. Xiao Ming has an electronic watch with a circular minute dial ((0, 1, \dots, n-1)). The watch originally only has a single button that increments the current minute by (1) (with (n-1+1=0)). If the watch shows a time that is (1) minute ahead of the desired time, one needs to press the button (n-1) times to adjust it back.

Now, imagine that the watch is upgraded with an additional button that adds (k) to the current minute (also modulo (n)). For example, if (n=10) and (k=6), starting from (0) two presses of the +(k) button will change the display to (2) (since (0+6=6) and then (6+6=12\equiv2 ; (\text{mod }10))).

Xiao Ming wants to know: using an optimal strategy, what is the maximum number of button presses required to adjust the watch from any starting minute to any target minute? In other words, for any two numbers in ({0,1,2,\dots,n-1}), if the minimal number of presses required (using operations of adding (1) or (k) modulo (n)) is taken, what is the maximum among all such pairs?

Formally, let (f(d)) be the minimum number of button presses needed to achieve a difference of (d) modulo (n) (where (d \in {0,1,\dots,n-1}) and the operations available are +1 and +(k)). You are to calculate (\max_{d=1}^{n-1} f(d)).

inputFormat

The input consists of a single line containing two integers (n) and (k) (with (n > 0) and (0 < k < n)), separated by a space.

outputFormat

Output a single integer — the maximum number of button presses required (over all pairs of distinct minutes) when using an optimal strategy.

sample

10 6

5