# 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β€a<bβ€10_{9})$, and the third line contains an integer $cΒ(2β€cβ€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β4β5β7$.

In the second example, the transitions can be performed as follows: $4β5β7β8β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.

($20$ points): $b,cβ€15$;

($30$ points): $b,cβ€10_{5}$;

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

($35$ points): $noΒadditionalΒconstraints$;