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