Марсохід, який здійснює міжнародну місію на Марсі, несправний. Для відновлення його працездатності необхідно підвищити потужність його батареї. Потужність батареї марсохода задається цілим додатним числом. Поточна потужність батареї дорівнює \(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