Un robot effectuant une mission internationale sur Mars est en panne. Pour rétablir son fonctionnement, il faut augmenter la puissance de sa batterie.

La puissance de la batterie du robot est un entier strictement positif. Sa puissance actuelle est $a$ et, pour rétablir le fonctionnement du robot, il faut la porter à $b$. Pour modifier la puissance de la batterie, on peut envoyer depuis la Terre deux types de signaux spéciaux : X et Y. Un signal de type X augmente la puissance actuelle de $1$, et un signal de type Y l’augmente de $2$.

Les organisateurs de la mission souhaitent atteindre la puissance nécessaire en envoyant le moins de signaux possible. Malheureusement, en raison de la conception du robot, si la puissance de sa batterie devient un multiple de l’entier $c$, le robot tombe définitivement en panne et cesse de répondre aux signaux.

Écrivez un programme qui, à partir de la puissance initiale $a$, de la puissance nécessaire $b$ et de l’entier $c$, détermine le nombre minimal de signaux à envoyer au robot pour rétablir son fonctionnement.

Entrée

L’entrée contient trois entiers, $a$, $b$ et $c$, un par ligne ($1 \le a < b \le 10^9$, $2 \le c \le 10^9$ ; ni $a$ ni $b$ ne sont multiples de $c$).

Sortie

Affichez un entier : le nombre minimal de signaux à envoyer au robot.

Exemples

Entrée 1

2
7
3

Sortie 1

3

Entrée 2

4
10
3

Sortie 2

4

Remarque

Dans le premier exemple, on peut envoyer au robot les signaux Y, X, Y. La puissance de la batterie évolue ainsi : $2 \to 4 \to 5 \to 7$.

Dans le deuxième exemple, on peut envoyer au robot les signaux X, Y, X, Y. La puissance de la batterie évolue ainsi : $4 \to 5 \to 7 \to 8 \to 10$.

Sous-tâches

Les points de chaque sous-tâche ne sont accordés que si tous les tests de cette sous-tâche et des sous-tâches requises sont réussis.