Faulty Mars Rover

The Mars rover, carrying out an international mission on Mars, is faulty. To restore its performance, it is necessary to increase the capacity of its battery.

The battery power of the rover is a positive integer. The current battery capacity is a, to restore the performance of the rover, it is necessary to increase its power to b. To change the battery power to the Mars rover from the Earth, you can send special signals of two types: X and Y. X type signal increases the current battery capacity by 1, and Y type signal increases the current battery capacity by 2.

The mission organisers would like to change the battery capacity to the required level by transmitting the minimum number of signals. Unfortunately, due to the peculiarity of the device of the rover, if the battery power is a multiple to an integer c, it finally fails and stops responding to signals.

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

Input

Three integers a, b and c, one in a line (1 ≤ a < b ≤ 10^9, 2 ≤ c ≤ 10^9, a is not divisible by c, b is not divisible by c).

Output

Print one integer: the minimum number of signals that must be transmitted to the rover.

Examples

Note

In the first example, you can act as follows: send signals to the rover Y, X, Y. Battery power varies as follows: 2 → 4 → 5 → 7.

In the second example, you can act as follows: send signals to the rover X, Y, X, Y. Battery power varies as follows: 4 → 5 → 7 → 8 → 10.