Ein Rover, der eine internationale Mission auf dem Mars ausführt, ist defekt. Um seine Funktionsfähigkeit wiederherzustellen, muss die Leistung seiner Batterie erhöht werden.

Die Batterieleistung des Rovers wird durch eine positive ganze Zahl beschrieben. Die aktuelle Leistung beträgt $a$ und muss auf $b$ erhöht werden, um die Funktionsfähigkeit des Rovers wiederherzustellen. Zur Änderung der Batterieleistung können von der Erde spezielle Signale zweier Typen, X und Y, an den Rover gesendet werden. Ein Signal vom Typ X erhöht die aktuelle Batterieleistung um $1$, ein Signal vom Typ Y um $2$.

Die Organisatoren der Mission möchten die erforderliche Batterieleistung mit möglichst wenigen Signalen erreichen. Leider fällt der Rover aufgrund seiner Konstruktion endgültig aus und reagiert nicht mehr auf Signale, sobald seine Batterieleistung ein Vielfaches der ganzen Zahl $c$ ist.

Schreibe ein Programm, das für die anfängliche Batterieleistung $a$, die erforderliche Batterieleistung $b$ und die ganze Zahl $c$ die minimale Anzahl von Signalen bestimmt, die an den Rover gesendet werden müssen, um seine Funktionsfähigkeit wiederherzustellen.

Eingabe

Die Eingabe enthält die drei ganzen Zahlen $a$, $b$ und $c$, jeweils in einer eigenen Zeile ($1 \le a < b \le 10^9$, $2 \le c \le 10^9$; weder $a$ noch $b$ ist ein Vielfaches von $c$).

Ausgabe

Gib eine ganze Zahl aus: die minimale Anzahl von Signalen, die an den Rover gesendet werden müssen.

Beispiele

Eingabe 1

2
7
3

Ausgabe 1

3

Eingabe 2

4
10
3

Ausgabe 2

4

Hinweis

Im ersten Beispiel kann man die Signale Y, X, Y senden. Die Batterieleistung ändert sich wie folgt: $2 \to 4 \to 5 \to 7$.

Im zweiten Beispiel kann man die Signale X, Y, X, Y senden. Die Batterieleistung ändert sich wie folgt: $4 \to 5 \to 7 \to 8 \to 10$.

Teilaufgaben

Die Punkte für jede Teilaufgabe werden nur vergeben, wenn alle Tests dieser Teilaufgabe und der erforderlichen Teilaufgaben bestanden werden.