Маленький Петя очень любит целые положительные числа. Недавно мама подарила ему целое положительное число a. Больше чем числа Петя любит только играть с маленькой Машей. Оказалось, что у Маши уже есть целое положительное число b. Петя решил превратить свое число a в число b, последовательно выполняя операции следующих двух типов:
- Вычесть из своего числа 1.
- Выбрать любое целое число x от 2 до k, включительно. Затем вычесть из своего числа a число (a mod x). Операция a mod x обозначает взятие остатка от деления числа a на число x.
Одну операцию Петя выполняет за одну секунду. Каждый раз он выбирает, какую операцию он будет выполнять на текущем ходу, независимо от того, какие операции он делал до этого. В частности, из этого следует, что он может выполнять одну и ту же операцию сколько угодно раз подряд.
Сейчас ему интересно, за какое наименьшее количество секунд он сможет превратить свое число a в число b. Обратите внимание, что числа x в операциях второго типа выбираются каждый раз заново, независимо друг от друга.
Примечание
В первом примере последовательность чисел, получающихся у Пети в процессе получения числа b, такая: 10 → 8 → 6 → 4 → 3 → 2 → 1.
Во втором примере одна из возможных последовательностей такая: 6 → 4 → 3.