Um veículo que realiza uma missão internacional em Marte está avariado. Para restabelecer o seu funcionamento, é necessário aumentar a potência da sua bateria.

A potência da bateria do veículo é representada por um inteiro positivo. A potência atual é $a$ e, para restabelecer o funcionamento do veículo, é necessário aumentá-la até $b$. Para alterar a potência da bateria, podem ser enviados da Terra sinais especiais de dois tipos: X e Y. Um sinal do tipo X aumenta a potência atual em $1$, e um sinal do tipo Y aumenta-a em $2$.

Os organizadores da missão desejam atingir a potência necessária enviando o menor número possível de sinais. Infelizmente, devido ao projeto do veículo, se a potência da bateria se tornar um múltiplo do inteiro $c$, o veículo avaria definitivamente e deixa de responder aos sinais.

Escreva um programa que, dadas a potência inicial $a$, a potência necessária $b$ e o inteiro $c$, determine o número mínimo de sinais que é necessário enviar ao veículo para restabelecer o seu funcionamento.

Entrada

A entrada contém três inteiros, $a$, $b$ e $c$, um por linha ($1 \le a < b \le 10^9$, $2 \le c \le 10^9$; nem $a$ nem $b$ são múltiplos de $c$).

Saída

Imprima um inteiro: o número mínimo de sinais que é necessário enviar ao veículo.

Exemplos

Entrada 1

2
7
3

Saída 1

3

Entrada 2

4
10
3

Saída 2

4

Nota

No primeiro exemplo, podem ser enviados os sinais Y, X, Y ao veículo. A potência da bateria muda assim: $2 \to 4 \to 5 \to 7$.

No segundo exemplo, podem ser enviados os sinais X, Y, X, Y ao veículo. A potência da bateria muda assim: $4 \to 5 \to 7 \to 8 \to 10$.

Subtarefas

Os pontos de cada subtarefa só são atribuídos se todos os testes dessa subtarefa e das subtarefas necessárias forem aprovados.