Несправний марсохід

Марсохід, що бере участь у міжнародній місії на Марсі, вийшов з ладу. Щоб відновити його функціональність, потрібно збільшити потужність його батареї.

Потужність батареї марсохода виражається цілим додатним числом. Наразі потужність батареї становить a, а для відновлення працездатності її потрібно збільшити до b. Для зміни потужності батареї з Землі можна надсилати спеціальні сигнали двох типів: X і Y. Сигнал типу X збільшує поточну потужність батареї на 1, а сигнал типу Y — на 2.

Організатори місії прагнуть змінити потужність батареї до необхідного рівня, використовуючи мінімальну кількість сигналів. Однак, через конструктивні особливості марсохода, якщо потужність батареї стає кратною числу c, він остаточно виходить з ладу і перестає реагувати на сигнали.

Напишіть програму, яка за заданими початковою потужністю батареї a, необхідною потужністю b і числом c визначає мінімальну кількість сигналів, які потрібно передати на марсохід для відновлення його працездатності.

Вхідні дані

Три цілі числа a, b і c, по одному на рядок (1 ≤ a < b ≤ 10^9, 2 ≤ c ≤ 10^9, a не кратне c, b не кратне c).

Вихідні дані

Виведіть одне ціле число: мінімальну кількість сигналів, які потрібно передати на марсохід.

Приклади

Примітка

У першому прикладі можна діяти так: відправити на марсохід сигнали Y, X, Y. Потужність батареї змінюється наступним чином: 2 → 4 → 5 → 7.

У другому прикладі можна діяти так: відправити на марсохід сигнали X, Y, X, Y. Потужність батареї змінюється наступним чином: 4 → 5 → 7 → 8 → 10.