该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

牛牛是货拉拉拉不拉拉布拉多部落的子民，货拉拉拉不拉拉布拉多部落共有n个村庄，被编号为1~n。由于货拉拉拉不拉拉布拉多部落比较落后，并不是每个村庄之间都有通路。货拉拉拉不拉拉布拉多部落的村庄间通路的规则是：每个村庄只会和它相邻的m个村庄之间有通路，且经过该通路的花费时间为两个村庄编号的最大公约数。

现在牛牛在1号村庄，想去n号村庄找酋长，已知每个村庄与它相邻的m个村庄之间有通路，按照如上规则，牛牛最少需要走多久才能到达n号村庄？

输入格式

输入数据只有一行，包括两个整数n和m （10 <= n <= 1000）（0 < m < min(n, 100)）

输出格式

输出一个数，表示牛牛从1号村庄到达n号村庄所花费的最短时间

样例

10 5

3

提示

对于样例，首先从1走到6，需要花费gcd(1, 6) == 1的时间

随后从6走到10, 需要花费gcd(6, 10) == 2的时间

一共花费的时间是3