Телевізор

У цей момент Бариш дивиться канал $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$ балів): немає додаткових обмежень;