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

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

Формат вхідних даних

Вхідні дані містять три цілих числа: ~a~, ~b~ і ~c~, по одному у рядку (~1 \le a < b \le 10^9~, ~2 \le c \le 10^9~, ~a~ не кратне ~c~, ~b~ не кратне ~c~).

Формат вихідних даних

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

Примітка

До прикладу 1:

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

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

Оцінювання

Підзадача 1: 25 балів, ~1 \le a < b \le 15, 2 \le c \le 15~

Підзадача 2: 25 балів, ~1 \le a < b \le 10^5, 2 \le c \le 10^5~

Підзадача 3: 25 балів, ~1 \le a < b \le 10^9, c = 2~

Підзадача 4: 25 балів, ~1 \le a < b \le 10^9, 2 \le c \le 10^9~

Приклад вхідних даних

2
7
3

Приклад вихідних даних

3

Приклад вхідних даних

4
10
3

Приклад вихідних даних

4