В настоящее время Барыш смотрит канал a по телевизору, но хочет переключиться на канал b (b>a), потому что там показывают интересный футбольный матч. Пульт от телевизора сломан, работают только две кнопки. При нажатии одной из этих кнопок телевизор переключается на канал с номером на 1 единицу больше, а при нажатии другой кнопки — телевизор переключается на канал с номером на 2 единицы больше. Барыш хочет быстро переключиться на канал с номером b, нажав минимальное количество кнопок, но есть проблема с каналами, номера которых в точности делится на число c, и в тот момент, когда Барыш переключает телевизор на такой канал, телевизор сломается.
Чему равно минимальное количество нажатий на кнопки, чтобы Барыш смог переключиться с канала номер a на канал номер b.
В первой строке дано целое число a, во второй строке дано целое число b (1≤a<b≤109) и в третьей строке дано целое число c (2≤c≤109). Гарантируется, что a и b не делятся на c.
Выведите минимальное количество нажатий на кнопки, чтобы Барыш смог переключиться с канала номер a на канал номер b.
В первом примере переходы могут быть выполнены следующим образом: 2→4→5→7.
Во втором примере переходы могут быть выполнены следующим образом: 4→5→7→8→10.
Данная задача состоит из 4-х подзадач. Баллы за подзадачу начисляются только в случае успешного прохождения всех тестов, связанных с этой подзадачой.
(20 баллов): b,c≤15;
(30 баллов): b,c≤105;
(15 баллов): c=2;
(35 баллов): нет дополнительных ограничений;