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

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

任务组织者希望发送尽可能少的信号，将电池功率提高到所需值。遗憾的是，由于火星车的设计特点，一旦电池功率成为整数 $c$ 的倍数，火星车就会彻底损坏，不再响应信号。

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

输入格式

输入包含三个整数 $a$、$b$ 和 $c$，每行一个（$1 \le a < b \le 10^9$，$2 \le c \le 10^9$，$a$ 和 $b$ 均不是 $c$ 的倍数）。

输出格式

输出一个整数：必须向火星车发送的最少信号数。

样例

输入格式 1

2
7
3

输出格式 1

3

输入格式 2

4
10
3

输出格式 2

4

说明

在第一个样例中，可以向火星车依次发送 Y、X、Y 信号。电池功率依次变化为 $2 \to 4 \to 5 \to 7$。

在第二个样例中，可以向火星车依次发送 X、Y、X、Y 信号。电池功率依次变化为 $4 \to 5 \to 7 \to 8 \to 10$。

子任务

只有通过某个子任务及其依赖子任务的全部测试，才能获得该子任务的分数。