题目描述

阿杰新买了一只电子计时器,正准备校准时间。

这款计时器在一个圆环上显示分钟数,共有 $n$ 个刻度(编号 $0$ 到 $n-1$),超过 $n-1$ 后会回到 $0$。

计时器只有一个「+1」按钮:当前刻度为 $x$ 时按一下变成 $(x+1)\bmod n$。

阿杰想,如果能再加一个「+k」按钮(按下后刻度变为 $(x+k)\bmod n$),调校效率会高很多。

他想知道:有了这两个按钮后,按照最优策略操作,从任意一个刻度调到另一个刻度,最多需要按多少次按钮？

注意:「+k」按钮按下后若超过 $n-1$,会对 $n$ 取模。例如 $n=10,k=6$ 时,从刻度 $0$ 连按两次「+6」会到达刻度 $2$。

输入格式

一行两个整数 $n,k$,意义如题。

输出格式

一行一个整数,表示按照最优策略操作,从一个刻度调到另一个刻度最多需要按多少次。

样例

5 3

2

提示

【样例解释】

如果当前刻度已正确则按 $0$ 次。否则各刻度需要的最少按键次数如下:

1. +1
2. +1, +1
3. +3
4. +3, +1

最多需要按 $2$ 次。

【数据范围】

对于 $30\%$ 的数据 $0 \lt k \lt n \le 5$。

对于 $60\%$ 的数据 $0 \lt k \lt n \le 100$。

对于 $100\%$ 的数据 $0 \lt k \lt n \le 10^5$。