A rover carrying out an international mission on Mars has malfunctioned. To restore its operation, its battery power must be increased.

The rover’s battery power is a positive integer. Its current power is $a$, and to restore the rover’s operation it must be increased to $b$. To change the battery power, special signals of two types, X and Y, can be sent to the rover from Earth. An X signal increases the current battery power by $1$, while a Y signal increases it by $2$.

The mission organizers would like to reach the required battery power by sending as few signals as possible. Unfortunately, because of the rover’s design, if its battery power becomes a multiple of the integer $c$, the rover fails permanently and stops responding to signals.

Write a program that, given the initial battery power $a$, the required battery power $b$, and the integer $c$, determines the minimum number of signals that must be sent to the rover to restore its operation.

Input

The input contains three integers, $a$, $b$, and $c$, one per line ($1 \le a < b \le 10^9$, $2 \le c \le 10^9$; neither $a$ nor $b$ is a multiple of $c$).

Output

Output one integer: the minimum number of signals that must be sent to the rover.

Examples

Input 1

2
7
3

Output 1

3

Input 2

4
10
3

Output 2

4

Note

In the first example, one can send the signals Y, X, Y to the rover. The battery power changes as follows: $2 \to 4 \to 5 \to 7$.

In the second example, one can send the signals X, Y, X, Y to the rover. The battery power changes as follows: $4 \to 5 \to 7 \to 8 \to 10$.

Subtasks

Points for a subtask are awarded only if all tests for that subtask and its required subtasks are passed.