C. Превращение числа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Петя очень любит целые положительные числа. Недавно мама подарила ему целое положительное число a. Больше чем числа Петя любит только играть с маленькой Машей. Оказалось, что у Маши уже есть целое положительное число b. Петя решил превратить свое число a в число b, последовательно выполняя операции следующих двух типов:

  1. Вычесть из своего числа 1.
  2. Выбрать любое целое число x от 2 до k, включительно. Затем вычесть из своего числа a число (a mod x). Операция a mod x обозначает взятие остатка от деления числа a на число x.

Одну операцию Петя выполняет за одну секунду. Каждый раз он выбирает, какую операцию он будет выполнять на текущем ходу, независимо от того, какие операции он делал до этого. В частности, из этого следует, что он может выполнять одну и ту же операцию сколько угодно раз подряд.

Сейчас ему интересно, за какое наименьшее количество секунд он сможет превратить свое число a в число b. Обратите внимание, что числа x в операциях второго типа выбираются каждый раз заново, независимо друг от друга.

Входные данные

В единственной строке записаны три целых числа a, b (1 ≤ b ≤ a ≤ 1018) и k (2 ≤ k ≤ 15).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

Выведите единственное целое число — искомое наименьшее количество секунд, необходимое для превращения числа a в число b.

Примеры
Входные данные
10 1 4
Выходные данные
6
Входные данные
6 3 10
Выходные данные
2
Входные данные
1000000000000000000 1 3
Выходные данные
666666666666666667
Примечание

В первом примере последовательность чисел, получающихся у Пети в процессе получения числа b, такая: 10  →  8  →  6  →  4  →  3  →  2  →  1.

Во втором примере одна из возможных последовательностей такая: 6  →  4  →  3.