Un vehículo que realiza una misión internacional en Marte se ha averiado. Para que vuelva a funcionar, hay que aumentar la potencia de su batería.

La potencia de la batería del vehículo se expresa mediante un entero positivo. La potencia actual es $a$ y, para restablecer el funcionamiento del vehículo, debe aumentarse hasta $b$. Para modificar la potencia de la batería, pueden enviarse desde la Tierra señales especiales de dos tipos: X e Y. Una señal de tipo X aumenta la potencia actual en $1$, y una señal de tipo Y la aumenta en $2$.

Los organizadores de la misión quieren alcanzar la potencia necesaria enviando el menor número posible de señales. Desgraciadamente, debido al diseño del vehículo, si la potencia de la batería se convierte en un múltiplo del entero $c$, el vehículo se avería definitivamente y deja de responder a las señales.

Escribe un programa que, dados la potencia inicial $a$, la potencia necesaria $b$ y el entero $c$, determine el número mínimo de señales que hay que enviar al vehículo para restablecer su funcionamiento.

Entrada

La entrada contiene tres enteros, $a$, $b$ y $c$, uno por línea ($1 \le a < b \le 10^9$, $2 \le c \le 10^9$; ni $a$ ni $b$ son múltiplos de $c$).

Salida

Imprime un entero: el número mínimo de señales que hay que enviar al vehículo.

Ejemplos

Entrada 1

2
7
3

Salida 1

3

Entrada 2

4
10
3

Salida 2

4

Nota

En el primer ejemplo se pueden enviar las señales Y, X, Y. La potencia de la batería cambia así: $2 \to 4 \to 5 \to 7$.

En el segundo ejemplo se pueden enviar las señales X, Y, X, Y. La potencia de la batería cambia así: $4 \to 5 \to 7 \to 8 \to 10$.

Subtareas

Los puntos de cada subtarea se conceden únicamente si se superan todas las pruebas de esa subtarea y de las subtareas necesarias.