Un rover impegnato in una missione internazionale su Marte è guasto. Per ripristinarne il funzionamento, è necessario aumentare la potenza della sua batteria.

La potenza della batteria del rover è rappresentata da un intero positivo. La potenza attuale è $a$ e, per ripristinare il funzionamento del rover, deve essere aumentata fino a $b$. Per modificare la potenza della batteria si possono inviare dalla Terra al rover segnali speciali di due tipi: X e Y. Un segnale di tipo X aumenta la potenza attuale di $1$, mentre un segnale di tipo Y la aumenta di $2$.

Gli organizzatori della missione vorrebbero raggiungere la potenza necessaria inviando il minor numero possibile di segnali. Purtroppo, a causa della struttura del rover, se la potenza della batteria diventa un multiplo dell’intero $c$, il rover si guasta definitivamente e smette di rispondere ai segnali.

Scrivi un programma che, date la potenza iniziale $a$, la potenza necessaria $b$ e l’intero $c$, determini il numero minimo di segnali da inviare al rover per ripristinarne il funzionamento.

Input

L’input contiene tre interi, $a$, $b$ e $c$, uno per riga ($1 \le a < b \le 10^9$, $2 \le c \le 10^9$; né $a$ né $b$ sono multipli di $c$).

Output

Stampa un intero: il numero minimo di segnali da inviare al rover.

Esempi

Input 1

2
7
3

Output 1

3

Input 2

4
10
3

Output 2

4

Nota

Nel primo esempio si possono inviare al rover i segnali Y, X, Y. La potenza della batteria cambia così: $2 \to 4 \to 5 \to 7$.

Nel secondo esempio si possono inviare al rover i segnali X, Y, X, Y. La potenza della batteria cambia così: $4 \to 5 \to 7 \to 8 \to 10$.

Sottoproblemi

I punti di ogni sottoproblema vengono assegnati solo se vengono superati tutti i test di quel sottoproblema e dei sottoproblemi richiesti.