Łazik wykonujący międzynarodową misję na Marsie jest uszkodzony. Aby przywrócić jego działanie, trzeba zwiększyć moc jego baterii.

Moc baterii łazika jest dodatnią liczbą całkowitą. Obecna moc wynosi $a$, a aby przywrócić działanie łazika, trzeba zwiększyć ją do $b$. W celu zmiany mocy baterii można przesyłać z Ziemi do łazika specjalne sygnały dwóch typów: X oraz Y. Sygnał typu X zwiększa obecną moc baterii o $1$, a sygnał typu Y zwiększa ją o $2$.

Organizatorzy misji chcą osiągnąć wymaganą moc baterii, wysyłając jak najmniej sygnałów. Niestety, ze względu na konstrukcję łazika, jeśli moc baterii stanie się wielokrotnością liczby całkowitej $c$, łazik ulegnie trwałemu uszkodzeniu i przestanie reagować na sygnały.

Napisz program, który na podstawie początkowej mocy baterii $a$, wymaganej mocy $b$ oraz liczby całkowitej $c$ wyznaczy minimalną liczbę sygnałów, które trzeba wysłać do łazika, aby przywrócić jego działanie.

Wejście

Wejście zawiera trzy liczby całkowite $a$, $b$ i $c$, po jednej w wierszu ($1 \le a < b \le 10^9$, $2 \le c \le 10^9$; ani $a$, ani $b$ nie są wielokrotnościami $c$).

Wyjście

Wypisz jedną liczbę całkowitą: minimalną liczbę sygnałów, które trzeba wysłać do łazika.

Przykład

Wejście 1

2
7
3

Wyjście 1

3

Wejście 2

4
10
3

Wyjście 2

4

Uwagi

W pierwszym przykładzie można wysłać do łazika sygnały Y, X, Y. Moc baterii zmienia się następująco: $2 \to 4 \to 5 \to 7$.

W drugim przykładzie można wysłać do łazika sygnały X, Y, X, Y. Moc baterii zmienia się następująco: $4 \to 5 \to 7 \to 8 \to 10$.

Podzadania

Punkty za każde podzadanie przyznaje się tylko wtedy, gdy zaliczone zostaną wszystkie testy tego podzadania oraz wymaganych podzadań.