题目描述

译自 ROI Regional 2019 Day2 T1. Неисправный марсоход

执行国际任务的火星车出现了故障。为了恢复其正常工作，需要提高其电池的功率。

火星车电池的功率用一个正整数表示。当前电池功率为 $a$，为了恢复火星车的工作，需要将其功率提高到 $b$。可以从地球向火星车发送两种类型的特殊信号来改变电池功率：$X$ 和 $Y$。$X$ 信号将当前电池功率增加 $1$，$Y$ 信号将当前电池功率增加 $2$。

任务的组织者希望通过发送最少数量的信号来将电池功率提高到所需的水平。不幸的是，由于火星车的设计特点，如果电池功率是整数 $c$ 的倍数，火星车将彻底失效并停止响应信号。

编写一个程序，根据给定的初始电池功率 $a$、所需的电池功率 $b$ 和整数 $c$，确定需要向火星车发送的最少信号数量，以恢复其正常工作。

输入格式

输入包含三个整数：$a$, $b$, $c$ $(1 \leq a < b \leq 10^9$，$2 \leq c \leq 10^9$，$a$ 不是 $c$ 的倍数，$b$ 不是 $c$ 的倍数），每行一个。

输出格式

输出一个整数，表示需要向火星车发送的最少信号数量。

样例 1

输入

2
7
3

输出

3

在第一个样例中，可以按以下方式操作：发送 $Y$、$X$、$Y$ 信号。电池功率变化如下：$2 \rightarrow 4 \rightarrow 5 \rightarrow 7$。

样例 2

输入

4
10
3

输出

4

在第二个样例中，可以按以下方式操作：发送 $X$、$Y$、$X$、$Y$ 信号。电池功率变化如下：$4 \rightarrow 5 \rightarrow 7 \rightarrow 8 \rightarrow 10$。

数据范围与提示

详细子任务附加限制及分值如下表所示。