TV

At the moment, Barysh is watching channel 𝑎 on TV but wants to switch to channel $b(b>a)$ because an interesting football match is showing there. The TV remote is broken, only two buttons work. When one of these buttons is pressed, the TV switches to a channel with a number $1$ unit higher, and when the other button is pressed, the TV switches to a channel with a number $2$ units higher. Barysh wants to quickly switch to channel $b$, pressing the minimum number of buttons, but there's a problem with channels whose numbers are exactly divisible by $c$. When Barysh switches the TV to such a channel, the TV breaks.

What is the minimum number of button presses for Barysh to switch from channel number $a$ to channel number $b$?

Input

The first line contains an integer $a$, the second line contains an integer $b(1\le a<b\le 10^9)$, and the third line contains an integer $c(2\le c\le 10^9)$. It is guaranteed that $a$ and $b$ are not divisible by $c$.

Output

Print the minimum number of button presses for Barysh to switch from channel number $a$ to channel number $b$.

Examples

In the first example, the transitions can be performed as follows: $2\to 4\to 5\to 7$.

In the second example, the transitions can be performed as follows: $4\to 5\to 7\to 8\to 10$.

Scoring

This problem consists of $4$ subtasks. Points for a subtask are awarded only if all the tests associated with that subtask are passed successfully.

1. ($20$ points): $b,c\le 15$;

2. ($30$ points): $b,c\le 10^5$;

3. ($15$ points): $c=2$;

4. ($35$ points): $noadditionalconstraints$;