一輛在火星執行國際任務的火星車發生了故障。為了恢復其正常運作，需要提高其電池功率。

火星車的電池功率是一個正整數。目前電池功率為 $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$。

子任務

只有通過某個子任務及其相依子任務的全部測試，才能獲得該子任務的分數。