Телевизор

В настоящее время Барыш смотрит канал $a$ по телевизору, но хочет переключиться на канал $b(b>a)$, потому что там показывают интересный футбольный матч. Пульт от телевизора сломан, работают только две кнопки. При нажатии одной из этих кнопок телевизор переключается на канал с номером на $1$ единицу больше, а при нажатии другой кнопки — телевизор переключается на канал с номером на $2$ единицы больше. Барыш хочет быстро переключиться на канал с номером $b$, нажав минимальное количество кнопок, но есть проблема с каналами, номера которых в точности делится на число $c$, и в тот момент, когда Барыш переключает телевизор на такой канал, телевизор сломается.

Чему равно минимальное количество нажатий на кнопки, чтобы Барыш смог переключиться с канала номер $a$ на канал номер $b$.

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

В первой строке дано целое число $a$, во второй строке дано целое число $b(1\le a<b\le 10^9)$ и в третьей строке дано целое число $c(2\le c\le 10^9)$. Гарантируется, что $a$ и $b$ не делятся на $c$.

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

Выведите минимальное количество нажатий на кнопки, чтобы Барыш смог переключиться с канала номер $a$ на канал номер $b$.

Примеры

В первом примере переходы могут быть выполнены следующим образом: $2\to 4\to 5\to 7$.

Во втором примере переходы могут быть выполнены следующим образом: $4\to 5\to 7\to 8\to 10$.

Оценивание

Данная задача состоит из $4$-х подзадач. Баллы за подзадачу начисляются только в случае успешного прохождения всех тестов, связанных с этой подзадачой.

1. ($20$ баллов): $b,c\le 15$;

2. ($30$ баллов): $b,c\le 10^5$;

3. ($15$ баллов): $c=2$;

4. ($35$ баллов): $нетдополнительныхограничений$;